Otwarte problemy na granicach TCS

W wątku Główne nierozwiązane problemy w informatyce teoretycznej? Iddo Tzameret napisał następujący doskonały komentarz:

Myślę, że powinniśmy rozróżnić między głównymi otwartymi problemami, które są postrzegane jako podstawowe problemy, takie jak $P\neq NP$ , i głównymi otwartymi problemami, które będą stanowić przełom techniczny, jeśli zostaną rozwiązane, ale niekoniecznie tak fundamentalne, np. Wykładnicze dolne granice $AC^0(6)$ Obwody C 0 ( 6 ) (tzn. Bramki ). Więc powinniśmy prawdopodobnie otworzyć nową wiki społeczności zatytułowaną „otwarte problemy na granicach TCS” lub podobną.$AC^0+\mod 6$

Ponieważ Iddo nie rozpoczął wątku, pomyślałem, że zacznę ten wątek.

Często główne otwarte problemy dziedzin są znane badaczom pracującym w powiązanych dziedzinach, ale moment, w którym utknęły obecne badania, jest nieznany osobom postronnym. Cytowany przykład jest dobry. Jako osoba z zewnątrz oczywiste jest, że jednym z największych problemów w złożoności obwodów jest wykazanie, że NP wymaga obwodów wielobiegunowych. Ale osoby z zewnątrz mogą nie zdawać sobie sprawy, że obecny punkt, w którym utknęliśmy, próbuje udowodnić wykładnicze dolne granice dla obwodów prądu przemiennego ⁰ z bramkami mod 6. (Oczywiście mogą występować inne problemy o złożoności obwodu o podobnej trudności, które opisują, gdzie utknęliśmy. Nie jest to unikalne.) Innym przykładem jest pokazanie dolnych granic czasoprzestrzeni dla SAT lepiej niż n ^1.801 .

Ten wątek dotyczy takich przykładów. Ponieważ trudno jest scharakteryzować takie problemy, podam tylko kilka przykładów właściwości takich problemów:

1. Często nie będą to duże otwarte problemy w tej dziedzinie, ale będą dużym przełomem, jeśli zostaną rozwiązane.
2. Zwykle nie jest to niewiarygodnie trudne, w tym sensie, że gdyby ktoś powiedział ci, że problem został rozwiązany wczoraj, nietrudno w to uwierzyć.
3. Problemy te często mają również liczby lub stałe, które nie są fundamentalne, ale powstają, ponieważ tak się dzieje, gdy utknęliśmy.
4. Problem na granicach danego pola będzie się od czasu do czasu zmieniał, w przeciwieństwie do największego problemu na polu, który pozostanie taki sam przez wiele lat.
5. Często te problemy są najłatwiejszymi, które są nadal otwarte. Na przykład nie mamy również wykładniczych dolnych granic dla AC ¹ , ale ponieważ [6] jest uwzględnione w tej klasie, formalnie łatwiej jest pokazać dolne granice dla [6], a zatem jest to obecna granica złożoności obwodu. A C $AC^0$$AC^0$

Proszę zamieścić jeden przykład na odpowiedź; obowiązują standardowe konwencje big-list i CW. Jeśli ktoś może wyjaśnić, jakiego rodzaju problemów szukamy lepiej niż ja, możesz edytować ten post i wprowadzić odpowiednie zmiany.

EDYCJA: Kaveh zasugerował, że odpowiedzi zawierają również wyjaśnienie, dlaczego dany problem znajduje się na granicy. Na przykład, dlaczego szukamy niższych granic dla AC ⁰ [6], a nie AC ⁰ [3]? Odpowiedź jest taka, że ​​mamy niższe limity względem AC ⁰ [3]. Ale oczywistym pytaniem jest, dlaczego te metody zawodzą w przypadku AC ⁰ [6]. Byłoby miło, gdyby odpowiedzi również mogły to wyjaśnić.

Oto trzy najkrótsze ścieżki badań:

O ( n + m log w ) 2 $1$ . Czy istnieje algorytm liniowy dla najkrótszych ścieżek z jednego źródła na wykresach skierowanych o nieujemnych wagach, przynajmniej w modelu obliczeniowym słowo-RAM? Zauważ, że istnieje algorytm liniowy dla grafów bezkierunkowych (patrz praca Thorupa). Na tej podstawie Hagerup ma czas działania dla ukierunkowanych wykresów z wagami ograniczonymi przez . Czy istnieje szybszy algorytm?$O(n+m\log w)$$2^w$

O ( n ω n ) ω < 2,376 O ( n 2,575 ) O ( n ω n $2$ . Czy istnieje algorytm polylog dla wszystkich par najkrótszych ścieżek na nieważonych grafach ukierunkowanych? ( jest wykładnikiem mnożenia macierzy) Bieżącym najlepszym środowiskiem uruchomieniowym jest firmy Zwick, a dla grafów bezkierunkowych problem można rozwiązać w polilog .$O(n^\omega$$n)$$\omega<2.376$$O(n^{2.575})$$O(n^\omega$$n)$

(Czy ukierunkowane problemy są rzeczywiście trudniejsze?)

O ( n 2,9 ) n 0 , … , $3$ . Czy istnieje algorytm dla wszystkich par najkrótszych ścieżek na wykresach węzłowych z wagami w { }? Czy też istnieje ograniczenie z ogólnego problemu najkrótszych ścieżek wszystkich par do tego ograniczenia?$O(n^{2.9})$$n$$0,\ldots,n$

Jest to już wspomniane w pytaniu:

Otwarty:

Oddzielić od ( obwody o głębokości 2). A C 0 2 [ 6 ] A C 0 [ 6 $EXP^{NP}$$AC^0_2[6]$$AC^0[6]$(patrz aktualizacja poniżej)

[Listopad 11, 2010] Oddziel od . Oddziel od .A C 0 2 [ 6 ] E X P N P T C $EXP$$AC^0_2[6]$$EXP^{NP}$$TC^0$

Znany:

1. [Alexander Razborov 1987 - Roman Smolensky 1987] nie ma w jeżeli jest liczbą pierwszą, a nie jest potęgą . A C 0 [ p k ] p m $MOD_m$$AC^0[p^k]$$p$$m$$p$

2. [Arkadev Chattopadhyay i Avi Wigderson 2009] Niech m, q będą liczbami całkowitymi w taki sposób, że m nie zawiera kwadratów i ma co najwyżej dwa czynniki pierwsze. Niech C będzie dowolnym obwodem typu gdzie jest bramką lub a bramki u podstawy mają dowolne zbiory akceptacji. Jeśli C oblicza to górny wachlarz, a zatem rozmiar obwodu, musi wynosić . G A N D O R M O D m M O D q 2 Ω ( n $MAJoGoMOD^A_m$$G$$AND$$OR$$MOD_m$$MOD_q$$2^{{\Omega(n)}}$

Późniejszy wynik opiera się na uzyskaniu wykładniczo małej korelacji związanej z funkcją z głębokości-2 i oszacowaniu sum wykładniczych obejmujących wielomiany niskiego stopnia.$MOD_q$

Przeszkody:?

Aktualizacja [listopada 10, 2010]

Papier przez Ryan Williams wydaje się być rozstrzygane ten problem przy użyciu otwartego metod, które wydają się być zasadniczo różne od tych wymienionych powyżej:

[Ryan Williams 2010] nie ma nierównomiernych obwodów o rozmiarze . A C C 0 2 n o ( 1 $E^{NP}$$ACC^0$$2^{n^{o(1)}}$

Bibliografia:

• AA Razborov. Dolne granice wielkości sieci głębokości ograniczonych na całej podstawie z dodaniem logicznym (rosyjski), w Matematicheskie Zametki, 41 (4): 598–607, 1987. Tłumaczenie na język angielski w notatkach matematycznych Akademii Nauk ZSRR, 41 (4): 333–338, 1987.

• R. Smoleński. Metody algebraiczne w teorii dolnych granic złożoności obwodu logicznego. W STOC, strony 77–82. ACM, 1987.

• Arkadev Chattopadhyay i Avi Wigderson. Systemy liniowe na modułach kompozytowych , FOCS 2009

• Ryan Williams. Obwód niejednolitego obwodu dolnego ACC , 2010, projekt (przesłany?).

Niech CNF-SAT będzie problemem ustalenia, czy dana formuła CNF jest zadowalająca (bez ograniczeń szerokości klauzul).

Czy CNF-SAT dla zmiennych i klauzul rozwiązywalny w czasie , dla niektórych ?m 2 δ n p o l y ( m ) δ < $n$$m$$2^{\delta n} poly(m)$$\delta < 1$

Jest to dobrze znany otwarty problem w dziedzinie „szybszych algorytmów dla NP”. Nie sądzę, że osiągnął status „głównego otwartego problemu”, ale przyciągnął sporo uwagi. Najbardziej znane algorytmy działają w czasie (np. Tutaj ).$2^{n-\Omega(n/\log (m/n))}$

W związku z hipotezą o wykładniczym czasie (że 3SAT nie ma czasu podwykładniczego) istnieje również „silna hipoteza o wykładniczym czasie”, zgodnie z którą optymalny czas działania dla SAT jest zbieżny z jako . Jedną z konsekwencji Strong-ETH byłoby to, że odpowiedź na powyższe pytanie brzmi „nie”. Kilka wiarygodnych hipotez sugeruje, że odpowiedź brzmi „tak” , ale kto wie.$k$$2^{n}$$k \rightarrow \infty$

Myślę, że jest to jeden z tych problemów, który wydaje się być „rozwiązany” w obu przypadkach: albo pokażemy odpowiedź „tak”, albo pokażemy, że odpowiedź „tak” oznacza coś bardzo ważnego. W pierwszym przypadku będziemy mieli satysfakcję z rozwiązania problemu, w drugim przypadku podniesiemy pytanie do „dużego otwartego problemu” ... brak odpowiedzi oznacza, że , i odpowiedź tak sugeruje coś bardzo ważnego. :)$P \neq NP$

Pytanie, czy drzewa decyzyjne można nauczyć się PAC, wydaje się znajdować na granicy teorii uczenia obliczeniowego.

OTWARTY

Czy PAC drzew decyzyjnych (DT) można się nauczyć w ramach jednolitego rozkładu na przykładach (lub ogólnie)?

ZNANY

• ID nie można się nauczyć w jednolitym rozkładzie za pomocą kwerend statystycznych (SQ) [ Blum i in. '94 ]
• losowe ID można się nauczyć w jednolitym rozkładzie [ Jackson, Servedio '05 ]
• monotoniczne ID można się nauczyć w jednolitym rozkładzie [ O'Donnell, Servedio '06 ]
• płynna analiza uczenia ID w jednolitym rozkładzie [ Kalai, Teng '08 ]

Powodem tego jest interesujący i ważny problem, ponieważ drzewa decyzyjne są bardzo naturalną klasą i w przeciwieństwie do, powiedzmy automatów, nie mamy wyników twardości kryptograficznej, które sprawiają, że problem jest beznadziejny. Postęp w tej kwestii może być może dać wgląd w to, czy ID (i podobne klasy) można się nauczyć bez założeń dystrybucyjnych. Może to mieć praktyczny wpływ, będąc przełomem teoretycznym.

Wydaje się, że problem ten rozwiązano również ze wszystkich stron. Wiemy, że zgodnie z jednolitym rozkładem na przykładach: drzewa decyzyjne monotoniczne są możliwe do nauczenia, że ​​drzewa decyzyjne losowe są łatwe do nauczenia, i że istnieje również płynna analiza. Wiemy również, że algorytm SQ nie rozwiąże tego problemu. Postępy w tym obszarze są również stałe. Z drugiej strony jest to trudny problem, który był otwarty od dłuższego czasu, więc wydaje się, że pasuje do projektu „Otwartych problemów na granicach TCS”.

Zauważ, że istnieją inne wyniki, których nie analizowałem na temat trudności prawidłowego uczenia się ID, umiejętności uczenia się ID za pomocą zapytań oraz na temat trudności uczenia się nawet przypadkowych ID za pomocą SQ.

OTWARTY:

Pokaż dolną granicę w modelu sondy komórkowej dla jawnego problemu ze statycznymi strukturami danych, który dowodzi, że przy pewnych „rozsądnych” ograniczeniach przestrzeni (np. Że przestrzeń ma wielomian wielkości wejściowej), czas zapytania musi wynosić najmniej T, gdzie T jest większy niż log | Q |, gdzie Q jest zbiorem zapytań. Nazywa się to „log | Q | -barrier” (lub czasami, w nieco mylący sposób, „bariera logn”).

ZNANY:

1. dolne granice wyższe niż log | Q | dla ukrytego problemu (patrz ankieta Miltersena )

2. dolne granice wyższe niż log | Q | z ekstremalnymi ograniczeniami przestrzeni (np. zwięzłe dolne granice)

3. dolne granice wyższe niż log | Q | dla problemów dynamicznych (gdzie mam na myśli, że jeśli czas aktualizacji jest bardzo krótki, to czas zapytania musi być bardzo duży lub odwrotnie; patrz np. dolna granica Patrascu dla częściowej sumy)

4. Dolne granice w ograniczonych modelach, takich jak maszyny wskaźnikowe, model porównawczy itp

5. dolne granice, które łamią log | Q | bariery nie można udowodnić standardowym rodzajem redukcji złożoności komunikacji, ponieważ Alicja może po prostu wysłać zapytanie, które zajmuje tylko log | P | bitów, a zatem łatwo jest zweryfikować, że redukcja nigdy nie da lepszej dolnej granicy niż ta. Zatem należy zastosować albo „natywny” związany z modelem sondy komórkowej, albo zastosować bardziej sprytne ograniczenie złożoności komunikacyjnej.

W klasach złożoności niskiego poziomu istnieje ciekawy problem z charakterystyką .$\mathsf{NL}$

OTWARTY:

Pokaż, czy jest równe .$\mathsf{NL}$$\mathsf{UL}$

$\mathsf{UL}$ , jednoznaczny obszar logów , to klasa składa się z problemów, które można rozwiązać za pomocą -machine z dodatkowym ograniczeniem, że istnieje co najwyżej jedna ścieżka obliczeniowa.$\mathsf{NL}$

ZNANY:

• W niejednorodnych okolicznościach . [RA00]$\mathsf{NL/poly} = \mathsf{UL/poly}$
• W ramach możliwych do przyjęcia założenia Twardość ( wymaga obwodów wykładnicze rozmiar), w wyniku [RA00] można derandomized pokazać, że . [ARZ99]$\mathsf{SPACE}(n)$$\mathsf{NL} = \mathsf{UL}$
• Osiągalność na 3-stronicowych wykresach jest kompletna dla . [PTV10]$\mathsf{NL}$
• Osiągalność na wykresach 2-stronicowych jest możliwa do rozwiązania dla . [BTV09]$\mathsf{UL}$
• Jeśli , to . [AJ93]$\mathsf{NL} = \mathsf{UL}$$\mathsf{FNL} \subseteq \mathsf{\sharp L}$

NIEZNANY:

• Klasa pośrednia , która jest zdefiniowana jako problemy rozwiązywane przez maszynę z co najwyżej wielomianowo wieloma ścieżkami obliczeniowymi, leży pomiędzy i . Nie są znane żadne zawalenia.$\mathsf{FewL}$$\mathsf{NL}$$\mathsf{NL}$$\mathsf{UL}$
• Wiadomo, że według słynnego twierdzenia Immermana-Szelepcsényiego, podczas gdy to, czy jest zamknięty pod dopełnieniem, jest nadal otwarte.$\mathsf{NL} = \mathsf{coNL}$$\mathsf{UL}$

Niektóre otwarte problemy PCP:

• Hipoteza w skali przesuwnej. W PCP chcemy, aby błąd weryfikatora był jak najmniejszy. BGLR wysunął hipotezę, że błąd może sięgać gdzie jest przypadkowością (wyraźnie istnieje dolna granica ). Cena, którą płacisz za zmniejszenie błędu, zwiększa tylko odpowiednio alfabet.$2^{-\Theta(r)}$$r$$2^{-r}$

Bardziej formalnie: przypuszczenie jest takie, że istnieje ac, taki że dla wszystkich naturalnych r, dla wszystkich istnieje weryfikator PCP, który używa losowości r do wykonania dwóch zapytań na dowód, ma doskonały błąd kompletności i poprawności . Alfabet dowodu zależy tylko od .$\varepsilon \geq 2^{-cr}$$\varepsilon$$1/\varepsilon$

W przypadku dwóch zapytań najbardziej znanym błędem jest dla niektórych określonych (M-Raz, 2008). Można również uzyskać błąd dla dowolnego , z szeregiem zapytań zależnych od (DFKRS).$1/r^{\beta}$$\beta>0$$2^{-r^{\alpha}}$$\alpha <1$$\alpha$

Poszukiwane są również dolne granice c (tj. Algorytmy aproksymacyjne).

Zobacz ankietę Irit Dinur, aby uzyskać więcej informacji.

• Długość liniowa PCP. Istnieją kody korygujące błędy o dużej odległości o długości liniowej. Czy istnieje PCP o długości liniowej?

W szczególności chcemy weryfikatora pod kątem zgodności z formułą SAT, która ma stałą liczbę zapytań, stały alfabet i stały błąd i ma dostęp do dowodu długości liniowej w długości formuły? Jest to otwarte nawet dla błędu bliskiego 1 (ale lepszego niż trywialny ), alfabetu sub wykładniczego i subliniowej liczby zapytań.$1-1/n$

Najbardziej znaną długością jest dla stałego błędu, a dla pod-stałego błędu.$n polylog n$$n \cdot 2^{(log n)^{1-\beta}}$

Udowodnij, że dla każdego istnieje język w , który nie ma (nierównomiernych) obwodów z drutami . Przypomnij sobie, że . Oznacza to, że udowodnij dolne granice obwodu superliniowego dla czasu wykładniczego z dostępem do wyroczni .$c > 0$$E^{NP}$$c n$$E = \bigcup_{k \geq 1} TIME[2^{k n}]$$NP$

A kod lokalnie dekodowalny (LDC) to mapa taka, że ​​istnieje algorytm , zwany dekoderem lokalnym , co, ze względu na wejściu liczbę całkowitą , a otrzymane słowo , który różni się od przez pewien o co najwyżej ułamek pozycji, wyszukuje co najwyżej współrzędne i wysyła z prawdopodobieństwem co najmniej . Mówi się, że LDC jest liniowe, jeśli$(q,\delta,\epsilon)$$C: \mathbb{F}^m \to \mathbb{F}^n$$A$$i \in [m]$$y \in \mathbb{F}^n$$C(x)$$x \in \mathbb{F}^m$$\delta$$q$$y$$x_i$$1/|\mathbb{F}| + \epsilon$$\mathbb{F}$jest polem, a jest -liniowy. LDC mają wiele zastosowań między innymi w teorii złożoności i prywatności.$C$$\mathbb{F}$

Dla i stałej sytuacja jest całkowicie rozwiązana. Kod Hadamarda jest liniowym zapytaniem LDC o wartości , i wiadomo, że jest zasadniczo optymalny, nawet dla nieliniowych LDC. Ale tutaj jest granicą! Jak tylko ustalimy , istnieje ogromna przerwa między znanymi górnymi i dolnymi granicami. Obecna najlepsza górna granica to liniowy kwerendowy LDC nad dowolnym skończonym polem (a nawet liczbami rzeczywistymi i kompleksami) ze złożonością zapytania [ Efremenko '09 , Dvir-Gopalan-Yekhanin '10 ]. Najlepsze dolne granice to$q=2$$\delta,\epsilon$$2$$n = \exp(m)$$q=2$$q=3$$3$$n=\exp(\exp(\sqrt{\log m \log \log m})) = 2^{m^{o(1)}}$$\Omega(m^2)$ dla liniowych zapytań LDC nad dowolnym polem i dla ogólnych zapytań LDC [ Woodruff '10 ]. Sytuacja w przypadku większej liczby zapytań jest jeszcze bardziej tragiczna.$3$$\Omega(m^2/\log m)$$3$

Jaka jest największa możliwa różnica między deterministycznymi a (dwustronnymi błędami ograniczonymi) kwantowymi złożonościami zapytań dla funkcji ogółem?

Otwarty:

Czy istnieje funkcja całkowita, której złożoność kwantowych zapytań wynosi T, a deterministyczna złożoność zapytań wynosi ω (T ² )?

Czy istnieje funkcja całkowita, której złożoność kwantowych zapytań wynosi T, a deterministyczna złożoność zapytań wynosi ω (T ⁴ )?

Jeśli całkowitą funkcję można obliczyć za pomocą zapytań T za pomocą algorytmu kwantowego, czy zawsze można ją obliczyć za pomocą zapytań za pomocą algorytmu deterministycznego?$o(T^6)$

Znany:

Jeśli złożoność kwantowego zapytania funkcji całkowitej wynosi T, to jej deterministyczna złożoność zapytania wynosi . (Odniesienie)$O(T^6)$

Największą znaną lukę osiąga funkcja OR, która osiąga lukę kwadratową.

Aktualizacja (21 czerwca 2015 r.) : Znamy teraz funkcję, która umożliwia rozdzielenie na kwartę (4. moc). Zobacz http://arxiv.org/abs/1506.04719 .

Przypuszcza się, że funkcja OR osiąga maksymalną możliwą przerwę.

Zgodnie z sugestią Ashleya dodam ten sam problem do dokładnego obliczenia.

Otwarty:

Czy istnieje funkcja całkowita, której dokładna złożoność kwantowych zapytań wynosi T, a której deterministyczna złożoność zapytań wynosi ?$\omega(T)$

Znany:

Jeśli dokładna kwantowa złożoność kwerendy funkcji całkowitej wynosi T, jej deterministyczna złożoność kwerendy wynosi . (Odniesienie)$O(T^3)$

Najbardziej znana różnica wynosi 2.

Aktualizacja (5 listopada 2012 r.) : Andris Ambainis poprawił przewagę superliniową dla dokładnych algorytmów kwantowych . Ze streszczenia: „Prezentujemy pierwszy przykład funkcji boolowskiej f (x_1, ..., x_N), dla której dokładne algorytmy kwantowe mają przewagę liniową nad algorytmami deterministycznymi. Każdy algorytm deterministyczny, który oblicza naszą funkcję, musi wykorzystywać zapytania N, ale dokładny algorytm kwantowy może go obliczyć za pomocą zapytań O (N ^ {0,8675 ...}). "

Istnieje wiele otwartych problemów w złożoności dowodu, wspomnę tylko o jednym, który pozostaje otwarty nawet po tym, jak niektórzy eksperci spędzili lata próbując go rozwiązać. Jest to wersja złożoności dowodu złożoności obwodu. (Zobacz [Segerlind07], jeśli chcesz zobaczyć więcej otwartych problemów w złożoności dowodu.)

otwarty

Udowodnij, że wielobiegunowy rozmiar dowodu wielobiegunowego jest niższy dla systemu dowodu Frege.$AC^0[2]$

$AC^0[2]$ -Frege (alias d-Frege + ) to system propozycji, który dopuszcza tylko obwody ( z ).$CG_2$$AC^0[2]$$AC^0$$\bmod 2$

Znany

1. Istnieją wielkości dolne wykładniczy dowód -Frege (znany jako stała głębokość Fregego, d-Frege) dla (propositional preparat gołębi otworami zasadniczo z gołębi dziury). Istnieją również wykładnicze dolne granice dla Frege + (stała głębokość Frege z liczeniem aksjomatów ). Wiadomo również, że Frege + nie są ograniczone wielomianowo.$AC^0$$PHP^{n+1}_{n}$$n+1$$n$$AC^0$$CA_p$$\bmod p$$AC^0$$CA_m$

2. Istnieją niższe wykładnicze wielkości obwodu dla odpowiedniej klasy obwodu, mianowicie .$AC^0[2]$

Bibliografia:

• Nathan Segerlind, „Złożoność dowodów dowodowych”, Bulletin of Symbolic Logic 13 (4), 2007

Otwarty:

Pokaż separator wyroczni między QIP (2) a AM. Oznacza to, że pokazują problem w QIP (2) ^A , która nie jest w AM ^A .

Dużym otwartym problemem jest wykazanie separacji wyroczni między BQP i PH. Ale nie mamy nawet rozdziału między BQP i AM (ponieważ AM jest w PH, powinno to być łatwiejsze). Co gorsza, uczyń BQP znacznie potężniejszym, pozwalając na 1 rundę interakcji z Merlinem, dając ci klasowe QAM lub QIP (2) (w zależności od monet publicznych lub prywatnych), a my nadal nie mamy separacji.

Znany:

Najbardziej znanym rozdziałem jest BQP i MA, który pochodzi z tego artykułu Johna Watrousa . Aby zapoznać się z klasami złożoności, które nie są klasami problemów decyzyjnych, zapoznaj się z wynikami Scott Aaronson .

Nie jestem pewien, czy należy to do klasy otwartych problemów granicznych czy poważnych otwartych problemów, więc komentarze są mile widziane.

Otwarty:

Pokaż, czy implikuje, że upada, czy nie.P $\mathsf{NP} = \mathsf{UP}$$\mathsf{PH}$

$\mathsf{UP}$ ( jednoznaczny czas wielomianowy) to klasa zdefiniowana jako problemy decyzyjne rozstrzygane przez maszynę NP z dodatkowym ograniczeniem, które

• istnieje co najwyżej jedna akceptująca ścieżka obliczeniowa na dowolnym wejściu.

Problem ten został stwierdzony na blogu złożoności w 2003 roku.

Znany:

Wynik przez Hemaspaandra, Naik, Ogiwara i Selman pokazuje, że jeśli posiada następujące oświadczenie, wówczas wielomian hierarchia wali do drugiego poziomu.

• Jest język takie, że dla każdego wzoru Sat, jest unikalny spełniającą zadanie o w . L ϕ x ( ϕ , x ) $\mathsf{NP}$$L$$\phi$$x$$(\phi,x)$$L$

Nieznany:

Wszelkie mało prawdopodobne zawalenia lub separacje.

Temat pokrewny: Więcej o klasach składniowych i semantycznych oraz UP vs NP .