Otwarte problemy na granicach TCS

58

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 PNP , 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 AC0(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ą.AC0+mod6

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 0 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 1 , 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 0AC0AC0

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 0 [6], a nie AC 0 [3]? Odpowiedź jest taka, że ​​mamy niższe limity względem AC 0 [3]. Ale oczywistym pytaniem jest, dlaczego te metody zawodzą w przypadku AC 0 [6]. Byłoby miło, gdyby odpowiedzi również mogły to wyjaśnić.

Robin Kothari
źródło
1
Czy chodzi tylko o teorię złożoności? Pytam, ponieważ w cytowanym wątku istnieje wiele problemów, które pasowałyby do podanego opisu tego pytania, a także nie miały bezpośredniego wpływu na P vs NP (odległość edycji, mnożenie macierzy itp.)
Suresh Venkat
Chciałem uwzględnić wszystkie TCS. Użyłem tylko przykładów złożoności, ponieważ to, co znam. Ten wątek będzie się nakładał, ponieważ ludzie zgłaszali poważne otwarte problemy i problemy na granicy naszej wiedzy.
Robin Kothari,
3
Myślę, że jest to doskonałe pytanie, o wiele bardziej interesujące i przydatne niż pytanie o „poważne otwarte problemy”. Dlatego postanowiłem rozpocząć nagrodę, chociaż to nie było moje pytanie. Nie jestem w 100% pewien, co się stanie, jeśli dam nagrodę za odpowiedź CW, ale zobaczymy to za 7 dni. :)
Jukka Suomela,
1
Dobry pomysł. Jestem również ciekawy, co się stanie, jeśli przyznasz nagrodę za odpowiedź CW.
Robin Kothari,
Nagroda została przyznana za aktualną, najwyższą odpowiedź. (Wygląda na to, że zadziałało zgodnie z oczekiwaniami; użytkownik, który opublikował odpowiedź CW, otrzymał +50 rep.)
Jukka Suomela

Odpowiedzi:

26

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

O ( n + m log w ) 2 w1 . 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+mlogw)2w

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ωn)ω<2.376O(n2.575)O(nωn)

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

O ( n 2,9 ) n 0 , , n3 . 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(n2.9)n0,,n

virgi
źródło
22

Jest to już wspomniane w pytaniu:

Otwarty:

Oddzielić od ( obwody o głębokości 2). A C 0 2 [ 6 ] A C 0 [ 6 ]EXPNPAC20[6]AC0[6](patrz aktualizacja poniżej)

[Listopad 11, 2010] Oddziel od . Oddziel od .A C 0 2 [ 6 ] E X P N P T C 0EXPAC20[6]EXPNPTC0

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 pMODmAC0[pk]pmp

  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 )MAJoGoMODmAGANDORMODmMODq2Ω(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.MODq

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 )ENPACC02no(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?).

Kaveh
źródło
1
Czy NP to największa klasa, o której nie wiadomo, że ściśle obejmuje [6]? AC0
Robin Kothari,
1
Myślę, że [6] tutaj odnosi się do niejednorodnej wersji klasy (w przeciwnym razie byłby ściśle zawarty w EXP, ponieważ jest zawarty w P). Być może ktoś może również dodać aktualny stan wiedzy dla wersji jednolitej. AC0
Robin Kothari,
4
Wyjaśnienie: To, czy znane są dolne granice dla obwodów głębokości 2, zależy przede wszystkim od dokładnej definicji bramek . Jeśli zdefiniujemy (jak to najczęściej się dzieje) wtedy i tylko wtedy, gdy wówczas dolne granice znane. Wchodzimy w obszar pytań otwartych, pozwalając na „ogólne” kryteria akceptacji, tj. które są 1, jeśli suma modulo 6 jest w dla niektórych . AC0\[6\]MOD6MOD6(x)=1xi0(mod6) A A { 0 , , 5 }MOD6AAA{0,,5}
Kristoffer Arnsfelt Hansen
2
Jeden dodatkowy punkt: jeśli zwiększysz głębokość z 2 do 3, wówczas rozróżnienie między bramkami nie ma już znaczenia ... żadne dolne granice nie są znane dla żadnego typu bramy. MOD6
Ryan Williams
11
Teraz ten jest rozliczony przez Ryana: cs.cmu.edu/~ryanw/acc-lbs.pdf . Gratulacje!!!
Hsien-Chih Chang 之 之
20

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 ) δ < 1nm2δnpoly(m)δ<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 ).2nΩ(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.k2nk

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. :)PNP

Ryan Williams
źródło
18

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

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.

Lew Reyzin
źródło
16

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.

Elad
źródło
1
Być może nie rozumiem pytania, ale skąd to wiadomo? „Dolne granice wyższe niż log | Q | dla problemów dynamicznych (odniesienie?)”
Mihai,
dodano odpowiednie odniesienie i wyjaśniono.
Elad
15

W klasach złożoności niskiego poziomu istnieje ciekawy problem z charakterystyką .NL

OTWARTY:

Pokaż, czy jest równe .NLUL

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.NL

ZNANY:

  • W niejednorodnych okolicznościach . [RA00]NL/poly=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]SPACE(n)NL=UL
  • Osiągalność na 3-stronicowych wykresach jest kompletna dla . [PTV10]NL
  • Osiągalność na wykresach 2-stronicowych jest możliwa do rozwiązania dla . [BTV09]UL
  • Jeśli , to . [AJ93]NL=ULFNLL

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.FewLNLNLUL
  • Wiadomo, że według słynnego twierdzenia Immermana-Szelepcsényiego, podczas gdy to, czy jest zamknięty pod dopełnieniem, jest nadal otwarte.NL=coNLUL
Hsien-Chih Chang 張顯 之
źródło
3
możesz dodać NL = coNL, jest to klasyczny wynik, ale jest powiązany.
Kaveh
1
@Kaveh: Czy chodzi ci o to, czy UL jest zamknięty w ramach dopełniacza?
Hsien-Chih Chang 之 之
1
Rozumiem! Przepraszam za nieporozumienie ... Zamiast tego umieściłem je w części NIEZNANE, za podkreślenie jako własności UL.
Hsien-Chih Chang 張顯 之
15

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Θ(r)r2r

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 .ε2crε1/ε

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ββ>02rαα<1α

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ń.11/n

Najbardziej znaną długością jest dla stałego błędu, a dla pod-stałego błędu.npolylognn2(logn)1β

Dana Moshkovitz
źródło
14

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>0ENPcnE=k1TIME[2kn]NP

Ryan Williams
źródło
Jaka jest najmniejsza klasa, dla której mamy dolne granice obwodu superliniowego?
Robin Kothari,
@Robin: Dobre pytanie. Tak naprawdę nie ma tutaj „wyjątkowego” minimum. W kategoriach „wielomianowych klas związanych” wiadomo, że klasa nie ma obwodów superliniowych. Można również udowodnić dolne granice obwodu superliniowego dla dla nieograniczonego . (Pozwólcie, że zostawię to jako ćwiczenie ... wskazówka: zbiór wszystkich obwodów o wielkości ma liczność .)S2PZPPNPTIME[2f(n)nlogn]fcn2O(nlogn)
Ryan Williams
14

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,δ,ϵ)C:FmFnAi[m]yFnC(x)xFmδqyxi1/|F|+ϵFjest polem, a jest -liniowy. LDC mają wiele zastosowań między innymi w teorii złożoności i prywatności.CF

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 toq=2δ,ϵ2n=exp(m)q=2q=33n=exp(exp(logmloglogm))=2mo(1)Ω(m2) 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Ω(m2/logm)3

rev arnab
źródło
13

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 2 )?

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

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(T6)

Znany:

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

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 ?ω(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(T3)

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 ...}). "

Robin Kothari
źródło
2
To także jeden z moich ulubionych otwartych problemów. Ale dodałbym również następujące pytanie: czy istnieje funkcja całkowita, której dokładna kwantowa złożoność zapytań wynosi T , a której deterministyczna złożoność zapytań wynosi ω (T) ? Najbardziej znana luka to czynnik 2. Uważam za szokujące, że jest to otwarty problem.
Ashley Montanaro,
11

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.AC0[2]

AC0[2] -Frege (alias d-Frege + ) to system propozycji, który dopuszcza tylko obwody ( z ).CG2AC0[2]AC0mod2

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.AC0PHPnn+1n+1nAC0CApmodpAC0CAm

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


Bibliografia:

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

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 .

Robin Kothari
źródło
4

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 HNP=UPPH

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 ) LNPLϕx(ϕ,x)L

Nieznany:

Wszelkie mało prawdopodobne zawalenia lub separacje.

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

Hsien-Chih Chang 張顯 之
źródło
Czy jakieś słabsze stwierdzenia są również otwarte? Na przykład, czy MA = UP oznacza załamanie? lub AM = UP?
Robin Kothari,
@Robin: Według mojej wiedzy nie. Ale jestem nowy w tym obszarze i nadal badam wyniki. Może pojawi się coś istotnego!
Hsien-Chih Chang 張顯 之