Jaka jest wyrocznia o minimalnej złożoności, która oddziela PSPACE od hierarchii wielomianowej?

17

tło

Wiadomo, że istnieje oracle tak, że .P S P A C E AP H AAPSPACEAPHA

Wiadomo nawet, że separacja dotyczy przypadkowej wyroczni. Nieformalnie można to interpretować w ten sposób, że istnieje wiele wyroczni, dla których i są osobne.P HPSPACEPH

Pytanie

Jak skomplikowane są te wyrocznie, które oddzielają od . W szczególności, czy istnieje wyrocznia taka, że ?P H A D T I M E ( 2 2 n ) P S P A C E AP H APSPACEPHADTIME(22n)PSPACEAPHA

Czy mamy jakąś wyrocznię taką, że i mają znaną złożoność górną granicę?P S P A C E AP H A AAPSPACEAPHAA

Uwaga: istnienie takiej wyroczni może mieć konsekwencje w teorii złożoności strukturalnej. Aby uzyskać szczegółowe informacje, zobacz poniższą aktualizację poniżej.

Zaktualizuj o szczegóły dotyczące techniki dolnej granicy

Twierdzenie: Jeśli , wówczas dla wszystkich wyroczniach , .A P / p o l y P S P A C E A = P H APSPACE=PHAP/polyPSPACEA=PHA

Szkic próbny: Załóżmy, że .PSPACE=PH

Niech zostanie podana wyrocznia . Możemy zbudować wielomianowy czas wyrocznia Maszyna Turinga która dla danej długości , zgaduje obwód o wielkości przy użyciu kwantyfikacji egzystencjalnej i sprawdza, czy obwód decyduje , porównując ocenę obwodu i wynik zapytania dla każdej długości ciąg przy użyciu uniwersalnej kwantyfikacji.Σ 2 M n p ( n ) A nAP/polyΣ2Mnp(n)An

Ponadto rozważ problem decyzyjny, który nazywam skwantyfikowanym obwodem boolowskim (QBC), w którym otrzymujesz skwantyfikowany obwód logiczny i chcesz wiedzieć, czy jest poprawny (podobny do QBF). Ten problem jest kompletny dla PSPACE, ponieważ QBF jest kompletny dla PSPACE.

Z założenia wynika, że ​​QBC . Powiedzmy, że dla jakiegoś wystarczająco dużego. Niech N oznacza czas wielomianowy \ Sigma_k Maszyna Turinga, która rozwiązuje QBC.Q B C Σ k k N Σ kPHQBCΣkkNΣk

Możemy przenikają wyliczenie M i N (podobny do tego, co odbywa się w dowodzie twierdzenia Karp-Lipton), aby uzyskać czas wielomianu Σk maszyna Turinga oracle, który rozwiązuje QBCA .

Nieoficjalnie, ta nowa maszyna przyjmuje jako wejście QBC wyrocznię (czyli QBC z bramkami wyroczni). Następnie oblicza obwód, który oblicza na wejściach o długości (jednocześnie odrywając pierwsze dwa kwantyfikatory). Następnie zastępuje bramy oracle oracle w QBC z obwodu do . Na koniec stosuje się pozostałą część algorytmu wielomianowego czasu do rozwiązywania w tej zmodyfikowanej instancji.n A Σ k Q B CAnAΣkQBC

Teraz możemy pokazać warunkową dolną granicę.

Następstwo: jeśli istnieje wyrocznia jak , to .P S P A C E AP H A N E X P P / p o l yANEXPPSPACEAPHANEXPP/poly

Dowód szkic: Załóżmy, że istnieje taki sposób, że . Jeśli , otrzymalibyśmy sprzeczność.P S P A C E AP H A N E X P P / p o l yANEXPPSPACEAPHANEXPP/poly

W szczególności, jeśli , to według powyższego twierdzenia mamy . Wiadomo jednak, że implikuje, że .NEXPP/polyPSPACEPHNEXPP/polyPSPACE=PH

(patrz tutaj, aby uzyskać szczegółowe informacje na temat znanych wyników dla P / poli)

Michael Wehar
źródło
3
Prawdopodobnie warto wspomnieć, że przypuszcza się, że PSPACE PH. tzn. trywialna wyrocznia zrobiłaby, ale po prostu nie możemy tego udowodnić.
Thomas wspiera Monikę
1
Jak dokładnie definiujesz relatywizowaną PSPACE? W literaturze pojawia się więcej niż jedna możliwość. W szczególności, czy zakłada się, że zapytania oracle są wielomianowo ograniczone?
Emil Jeřábek wspiera Monikę
1
Czy dołączasz „Konstrukcja formuł Q”, duże monotoniczne formuły boolowskie, które decydują o wszystkich 2 ^ qbfach oryginalnej formuły, w PH? Więcej informacji na temat formuł Q można znaleźć we Wstępie do QSpace, Konferencja Satisfiable 2002, Międzynarodowe warsztaty na temat QBFS.
Daniel Pehoushek
1
Wierzę, że mogę wykazać, jako dolną granicę, że taka istota w SEH „miałaby konsekwencje w teorii złożoności strukturalnej”. Czy powinienem opublikować to dość wcześnie (co może oznaczać jutro lub może za 30 minut), czy też zostawić to bez odpowiedzi dłużej, aby bardziej prawdopodobne było uzyskanie odpowiedzi z zajęciami, które wystarczą? A
1
Biorąc pod uwagę, że losowe wyrocznie mają wysoką złożoność Kołmogorowa, oczekiwałbym, że jakakolwiek obliczalna górna granica takich wyroczni będzie miała znaczące konsekwencje. Silne górne granice, takie jak pojedyncze wykładnicze, powinny mieć poważne konsekwencje. (Oczywiście ten argument jest czysto heurystyczny i obecnie nie mam pojęcia, jak uczynić go rygorystycznym.)
András Salamon

Odpowiedzi:

9

Uważam, że jeśli przejrzysz podany argument, np. W sekcji 4.1 ankiety Ker-I Ko , otrzymasz górną granicę . W rzeczywistości możemy zastąpić n 2 dowolną funkcją n f ( n ), gdzie f ( n ) jako n . Nie do końca o to poproszono, ale jest blisko.DTIME(22O(n2))n2nf(n)f(n)n

W szczególności, korzystając z translacji między separacjami wyroczni i dolnymi granicami obwodu oraz zgodnie z notacją Ko, otrzymujemy:

  • Przekątnimy na ciągi o długości gdzie p n ( x ) = x n + n jest „ n ” wielomianem (w niektórych wyliczeniach algorytmów wieloczasowych) i m ( n ) zostanie określone poniżej.t(n)=pn(m(n))pn(x)=xn+nnm(n)

  • Przekładając się na dolne granice obwodu, oznacza to, że rozważamy obwody o ograniczonej głębokości na wejściach .2t(n)

  • Wymóg (patrz str. 15 Ko) potrzebujemy aby spełnić 1m(n)dla wszystkichn. Tutajdjest głębokość obwodów chcemy diagonalize przeciw, lub równoważnie poziomieĎ p d oPHchcemy diagonalize przeciw. Aby diagonalize przeciwko wszystkimPH, wystarczy wybraćdbyć funkcjąntoω(1); możemy wybrać takid1102m/(d1)>dpn(m(n))ndΣdpPHPHdnω(1)drośnie jednak dowolnie powoli (być może z zastrzeżeniem pewnych założeń obliczeniowych dla , ale nie powinno to stanowić przeszkody). Jeśli zgadniemy, że d ( n ) jest stałe (chociaż tak nie jest, ale będzie rosło dowolnie powoli), to widzimy, że m ( n ) około 2 n powinno działać.d(n)d(n)m(n)2n

  • Oznacza to, że , więc szukamy dolnej granicy względem obwodów z wejściami 2 2 n 2 .t(n)2n222n2

  • Trevisan Xue (CCC '13) wykazały, że można znaleźć przypisania w którym dany obwód ograniczony głębokości na wejść na Nie obliczeniową parzystości z nasiona P ° l y l O g ( N ) długości.Npolylog(N)

  • Dla nas , więc p o l y l o g ( N ) = 2 O ( n 2 ) . Możemy brutalizować siłę nad takimi nasionami w czasie 2 2 O ( n 2 ) i użyć pierwszego, który działa.N=22n2polylog(N)=2O(n2)22O(n2)

Zastąpić z n f ( n ) , daj s n ( x ) = x f ( n ) + f ( n ) , a nie.n2nf(n)pn(x)=xf(n)+f(n)

Co ciekawe, jeśli dobrze rozumiem, uważam, że oznacza to, że gdyby można było ulepszyć Trevisan-Xue ...

  • ... do algorytmu pseudodeterministycznego / Bellagio (patrz komentarz Andrew Morgana poniżej), można by uzyskać, że ; lubBPEXPP/poly

  • ... do niedeterministycznych algorytmu domyślić bitów, lecz następnie biegła w P ° l r ( N ) czasu, a taki sposób, że w każdej przyjmującej ścieżki sprawia, że taki sam wynik ( por N P S V ), to oznacza, N E X PP / p o, l y ; lubpolylog(N)poly(N)NPSVNEXPP/poly

  • ... do algorytmu deterministycznego można uzyskać .EXPP/poly

Z jednej strony sugeruje to, dlaczego dalsza derandomizacja przełączającego lematu powinna być trudna - argument, którego nie jestem pewien, był znany wcześniej! Z drugiej strony wydaje mi się to ciekawym podejściem do twardości kontra losowości (czy to rzeczywiście nowa rzecz, wyrocznie kontra losowość?).

Joshua Grochow
źródło
3
Jednym z wyzwań, które tu się rzuca, jest to, że zbudowana wyrocznia musi być pojedynczą, stałą wyrocznią, tak aby decyzja była w BPEXP lub czymkolwiek. Jeśli po prostu wybierzesz losowe ziarno dobrego generatora, wtedy, gdy dostaniesz jakąś wyrocznię, która działa, niekoniecznie otrzymasz procedurę decyzyjną dla tej wyroczni, ponieważ różne nasiona dają (ogólnie) różne wyrocznie. Będziesz musiał zrobić coś więcej, na przykład znaleźć ziarno kanoniczne, aby konstrukcja była rzeczywiście „konstruktywna”.
Andrew Morgan,
3
Nawet jeśli argument nie podaje BPEXP, czy możesz sprowadzić złożoność do skończonego poziomu EXPH?
Emil Jeřábek wspiera Monikę
2
@ EmilJeřábek: Myślę, że bez sprawdzania szczegółów powinno działać. Odgadnij ziarno za pomocą , sprawdź, czy działa za pomocą , a następnie sprawdź, czy jest to leksykograficznie najmniej ziarno, używając ¬ = ¬ , w sumie . Σ3EXP¬=¬
Joshua Grochow
2
@EmilJerabek: Oczywiście, gdybyśmy mogli przynajmniej sprowadzić to do , byłoby to jeszcze lepsze (niemożliwe do ulepszenia bez udowodnienia nowych granic dolnych obwodów), ale jeszcze nie wiem, jak to zrobić ...MAEXP
Joshua Grochow
2
@JoshuaGrochow Tak, twój oryginalny post wydaje się w porządku. Sprzeciwiłem się Pańskiej odpowiedzi Emilowi, która wysunęła hipotezę, że wyroczni można dokonać w EXPH, gdzie czas działania jest jednoznacznie wykładniczy. Z perspektywy czasu powinienem był wyrazić się lepiej.
Andrew Morgan