tło
Wiadomo, że istnieje oracle tak, że .P S P A C E A ≠ P H 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 H
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 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
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 A
Szkic próbny: Załóżmy, że .
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 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 Σ k
Możemy przenikają wyliczenie i (podobny do tego, co odbywa się w dowodzie twierdzenia Karp-Lipton), aby uzyskać czas wielomianu maszyna Turinga oracle, który rozwiązuje .
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 C
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 y
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 y
W szczególności, jeśli , to według powyższego twierdzenia mamy . Wiadomo jednak, że implikuje, że .
(patrz tutaj, aby uzyskać szczegółowe informacje na temat znanych wyników dla P / poli)
źródło
Odpowiedzi:
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)) n2 nf(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+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 .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/(d−1)>dpn(m(n)) n d Σpd PH PH d n ω(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) 2n
Oznacza to, że , więc szukamy dolnej granicy względem obwodów z wejściami ∼ 2 2 n 2 .t(n)∼2n2 ∼22n2
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=22n2 polylog(N)=2O(n2) 22O(n2)
Zastąpić z n f ( n ) , daj s n ( x ) = x f ( n ) + f ( n ) , a nie.n2 nf(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 ; lubBPEXP⊈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 ; lubpolylog(N) poly(N) NPSV NEXP⊈P/poly
... do algorytmu deterministycznego można uzyskać .EXP⊈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ść?).
źródło