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

tło

Wiadomo, że istnieje oracle tak, że .P S P A C E A ≠ P H $A$$PSPACE^A \neq PH^A$

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 $PSPACE$$PH$

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 A ≠ P H $PSPACE$$PH$$A \in DTIME(2^{2^{n}})$$PSPACE^A \neq PH^A$

Czy mamy jakąś wyrocznię taką, że i mają znaną złożoność górną granicę?P S P A C E A ≠ P H A$A$$PSPACE^A \neq PH^A$$A$

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 $PSPACE = PH$$A \in P/poly$$PSPACE^A = PH^A$

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 $A \in P/poly$$\Sigma_2$$M$$n$$p(n)$$A$$n$

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 Σ $\in PH$$QBC \in \Sigma_k$$k$$N$$\Sigma_k$

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

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 $A$$n$$A$$\Sigma_k$$QBC$

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

Następstwo: jeśli istnieje wyrocznia jak , to .P S P A C E A ≠ P H A N E X P ⊈ P / p o l $A \in NEXP$$PSPACE^A \neq PH^A$$NEXP \nsubseteq P/poly$

Dowód szkic: Załóżmy, że istnieje taki sposób, że . Jeśli , otrzymalibyśmy sprzeczność.P S P A C E A ≠ P H A N E X P ⊆ P / p o l $A \in NEXP$$PSPACE^A \neq PH^A$$NEXP \subseteq P/poly$

W szczególności, jeśli , to według powyższego twierdzenia mamy . Wiadomo jednak, że implikuje, że .$NEXP \subseteq P/poly$$PSPACE \neq PH$$NEXP \subseteq P/poly$$PSPACE = PH$

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

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.$\mathsf{DTIME}(2^{2^{O(n^2)}})$$n^2$$nf(n)$$f(n) \to \infty$$n \to \infty$

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) = p_n(m(n))$$p_n(x) = x^n + n$$n$$m(n)$

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

• Wymóg (patrz str. 15 Ko) potrzebujemy aby spełnić $m(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ć taki$\frac{1}{10} 2^{m/(d-1)} > d p_n(m(n))$$n$$d$$\mathsf{\Sigma_d^p}$$\mathsf{PH}$$\mathsf{PH}$$d$$n$$\omega(1)$$d$roś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)$$2^n$

• Oznacza to, że , więc szukamy dolnej granicy względem obwodów z wejściami ∼ 2 2 n 2 .$t(n) \sim 2^{n^2}$$\sim 2^{2^{n^2}}$

• 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.$N$$polylog(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=2^{2^{n^2}}$$polylog(N) = 2^{O(n^2)}$$2^{2^{O(n^2)}}$

Zastąpić z n f ( n ) , daj s n ( x ) = x f ( n ) + f ( n ) , a nie.$n^2$$nf(n)$$p_n(x) = x^{f(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 ; lub$\mathsf{BPEXP} \not\subseteq \mathsf{P/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 P ⊈ P / p o, l y ; lub$polylog(N)$$poly(N)$$\mathsf{NPSV}$$\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$

• ... do algorytmu deterministycznego można uzyskać .$\mathsf{EXP} \not\subseteq \mathsf{P/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ść?).