Pytania otagowane jako lower-bounds

pytania o dolne granice funkcji, zwykle złożoność algorytmu lub problem

2
Czy istnieje wytłumaczenie trudności w udowodnieniu kwadratowych dolnych granic dla interesujących problemów NP?
To kontynuacja mojego poprzedniego pytania: Najbardziej znana deterministyczna złożoność czasu dolna granica naturalnego problemu w NP Uważam za zdumiewające, że nie byliśmy w stanie udowodnić żadnego kwadratowego deterministycznego czasu w dolnej granicy jakiegokolwiek interesującego problemu NP, na który ludzie dbają i starają się zaprojektować lepsze algorytmy. Nasza hipoteza o wykładniczym …
4
Dolna granica dla testowania bliskości w normie ?
Zastanawiałem się, czy istnieje jakakolwiek dolna granica (pod względem złożoności próby) znana z następującego problemu: Biorąc pod uwagę przykładowy dostęp do wyroczni do dwóch nieznanych dystrybucji , D_2 w \ {1, \ dots, n \} , test (whp) czyD1D1D_1D2D2D_2{1,…,n}{1,…,n}\{1,\dots,n\} D1=D2D1=D2D_1=D_2 lub d2(D1,D2)=∥D1−D2∥2=∑ni=1(D1(i)−D2(i))2−−−−−−−−−−−−−−−−−−√≥ϵd2⁡(D1,D2)=‖D1−D2‖2=∑i=1n(D1(i)−D2(i))2≥ϵ\operatorname{d_2}(D_1,D_2)=\lVert D_1-D_2\rVert_2 = \sqrt{\sum_{i=1}^n\left(D_1(i)-D_2(i)\right)^2} \geq \epsilon Batu i in. …
1
Dolne granice uczenia się w zapytaniu o członkostwo i modelu kontrprzykładowym
Dana Angluin ( 1987 ; pdf ) definiuje model uczenia się z zapytaniami o członkostwo i teoriami (kontrprzykłady do proponowanej funkcji). Pokazuje, że zwykły język reprezentowany przez minimalny DFA z stanów jest możliwy do nauczenia się w czasie wielomianowym (gdzie proponowane funkcje to DFA) z zapytaniami o członkostwo i co …
1
Dolne granice niedeterministycznej komunikacji wielostronnej
Jest to kontynuacja mojego poprzedniego pytania dotyczącego dolnych granic komunikacji dla częściowych funkcji boolowskich . Czy ktoś może zasugerować jakieś odniesienie do dolnych granic niedeterministycznej komunikacji wielopartyjnej? Przeglądam dokumenty w terenie, ale wydaje się, że wszyscy wykazują separacje następującego typu: dolna granica dla protokołu losowego i (mniejsza) górna granica dla …
1
Używasz złożoności Kołmogorowa, aby ustalić dolne granice złożoności dowodu?
Motywacją tego pytania jest fakt, że większość ciągów n-bitowych jest nieściśliwa. Intuicyjnie możemy zaproponować przez analogię, że większość dowodów dla tautologii jest nieściśliwa dla wielkości wielomianowej. Zasadniczo, moja intuicja jest taka, że ​​niektóre dowody są z natury losowe i nie można ich skompresować. Czy istnieje dobre odniesienie do wysiłków badawczych …
2
2DFA, która wymaga wielu stanów w równoważnym DFA?
Czy istnieje 2DFA ze stanami (gdzie n nie jest łatwe, powiedzmy co najmniej 4), które wymagają co najmniej 2 n stanów do symulacji przy użyciu dowolnego DFA?nnnnnn2)n2n2^n Dwukierunkowy DFA (2DFA) jest deterministyczny automat skończony-państwo, które może poruszać się tam iz powrotem na jej taśmie tylko do odczytu wejścia, w przeciwieństwie …
1
Ile rozcięć krawędzi musi mieć DAG?
Następujące pytanie jest związane z optymalności Bellmana-Forda - najkrótsza droga algorytm programowania dynamicznego (patrz ten post dla połączenia). Pozytywna odpowiedź sugerowałaby również, że minimalny rozmiar monotonicznego niedeterministycznego programu do rozgałęziania dla problemu STCONN to . tssstttΘ(n3)Θ(n3)\Theta(n^3) Niech być DAG (skierowane acykliczny wykres) z jednym węzłem źródłowym jeden docelowego węzła . …
2
Co się stanie, jeśli poprawimy twierdzenia dotyczące hierarchii czasu?
f,gf,gf,gf(n)logf(n)=o(g(n))f(n)log⁡f(n)=o(g(n))f(n) \log f(n) = o(g(n))f , g f ( n + 1 ) = o ( g ( n ) )DTIME(f(n))⊊DTIME(g(n))DTIME(f(n))⊊DTIME(g(n)) DTIME(f(n)) \subsetneq DTIME(g(n))f,gf,gf,gf(n+1)=o(g(n))f(n+1)=o(g(n))f(n+1)=o(g(n))jest to NTIME(f(n))⊊NTIME(g(n)).NTIME(f(n))⊊NTIME(g(n)). NTIME(f(n)) \subsetneq NTIME(g(n)). Istnieje wiele (starych i aktualnych) wyników, które wykorzystują twierdzenia o hierarchii czasu do udowodnienia dolnych granic. Oto moje pytania: Co się …
2
Dolne granice dla liniowego problemu satysfakcji
W SODA 1995 Jeff Erickson wykazały niższe granice liniowego spełnialności (sprawdzenie, czy niektóre -subset z n liczb rzeczywistych spełnia równanie liniowe o r zmiennych). Metoda dowodowa wykorzystuje nieskończenie małe i zasadę transferu Tarskiego .rrrnnnrrr Czy ktoś mógłby wyjaśnić intuicję, jaką kryje się za tą trasą, aby udowodnić tę granicę? Jaka …
1
Czy złożoność Kołmogorowa w tabelach prawdy problemu zatrzymania jest znana asymptotycznie?
Pozwolić HALTnHALTnHALT_n oznacz ciąg długości 2n2n2^n odpowiadający tabeli prawdy problemu zatrzymania dla danych wejściowych długości nnn. Jeśli sekwencja złożoności Kołmogorowa K(HALTn)K(HALTn)K(HALT_n) byli O(1)O(1)O(1), wtedy jeden z ciągów porad byłby używany nieskończenie często, a TM z tym ciągiem zakodowanym na stałe byłby w stanie rozwiązać HALTHALTHALT równomiernie nieskończenie często, o czym …
2
Jaka jest „najmniejsza” klasa złożoności, dla której
Wierzę, że odpowiedzi na to pytanie dają takie klasy, że dla wszystkich wielomianówppp, w klasie występuje problem, który nie ma obwodów wielkościp ( n )p(n)p(n). Pytam jednak o rozmiar obwoduω( n )ω(n)\omega \hspace{.02 in}(n). (⟨00,11,2)2),3)1,44,51,66,71,88,91, . . .⟩(⟨00,11,22,31,44,51,66,71,88,91,...⟩\big(\hspace{-0.07 in}\left\langle \hspace{-0.04 in}0^{\hspace{.02 in}0}\hspace{-0.03 in},\hspace{-0.04 in}1^{\hspace{-0.03 in}1}\hspace{-0.03 in},2^{\hspace{.02 in}2}\hspace{-0.04 in},\hspace{-0.03 in}3^1\hspace{-0.04 in},\hspace{-0.03 …
2
Dolna granica liczby wezwań wyroczni do rozwiązania przypadków problemu zatrzymania
Spotkałem następujące pytanie, które jest łatwym ćwiczeniem (spoiler poniżej). Dostajemy wystąpień problemu z zatrzymaniem (np. TM ) i musimy dokładnie zdecydować, które z nich zatrzymają się na . Oznacza to, że musimy . Dostajemy wyrocznię za problem zatrzymania, ale musimy go użyć minimalną liczbę razy.nnnM1,...,MnM1,...,MnM_1,...,M_nϵϵ\epsilon{i:Mi halts on ϵ}{i:Mi halts on …
1
Czy możemy uzyskać posortowaną listę z posortowanej macierzy w
Jestem zmieszany. Chcę udowodnić, że problem sortowania macierzy przez , tj. Wiersze i kolumny są w porządku rosnącym, to . Kontynuuję, zakładając, że można to zrobić szybciej niż i próbuję złamać dolną granicę Dla porównań potrzebnych do posortowania m elementów. Mam dwie sprzeczne odpowiedzi:nnnnnnΩ (n2)logn )Ω(n2)log⁡n)\Omega(n^2\log n)n2)lognn2)log⁡nn^2\log nlog( m ! …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.