Hierarchia dla BPP a derandomizacja

W jednym zdaniu: czy istnienie hierarchii dla oznaczałoby jakiekolwiek wyniki derandomizacji?$\mathsf{BPTIME}$

Powiązane, ale niejasne pytanie brzmi: czy istnienie hierarchii dla implikuje jakieś trudne dolne granice? Czy rozwiązanie tego problemu uderza w znaną barierę w teorii złożoności?$\mathsf{BPTIME}$

Moim motywem do tego pytania jest zrozumienie względnej trudności (w odniesieniu do innych głównych otwartych problemów w teorii złożoności) wykazania hierarchii dla . Zakładam, że wszyscy uważają, że taka hierarchia istnieje, ale proszę, popraw mnie, jeśli uważasz inaczej.$\mathsf{BPTIME}$

Pewne tło : $\mathsf{BPTIME}(f(n))$ zawiera te języki, o których członkostwie decyduje probabilistyczna maszyna tokarska w czasie $f(n)$ z ograniczonym prawdopodobieństwem błędu. Mówiąc dokładniej, język $L \in \mathsf{BPTIME}(f(n))$ jeżeli istnieje probabilistyczna maszyna Turinga $T$ taka, że ​​dla dowolnego maszyna działa w czasieT O ( f ( | x | ) $x \in L$$T$$O(f(|x|))$ i przyjmuje z prawdopodobieństwem co najmniej , a dla każdego , biegnie w czasie i odrzuca z prawdopodobieństwem co najmniej .x ∉ L T O ( f ( | x | ) ), 2 /$2/3$$x \not \in L$$T$$O(f(|x|))$$2/3$

Bezwarunkowo jest otwarte, czy dla wszystkich . Barak pokazał, że istnieje ścisła hierarchia dla komputerów z . Fortnow i Santhanam poprawili to do 1 odrobiny porad. To prowadzi mnie do myślenia, że ​​udowodnienie istnienia probabilistycznej hierarchii czasu nie jest tak dalekie. Z drugiej strony wynik jest nadal otwarty i nie mogę znaleźć żadnego postępu po 2004 r. Referencje, jak zwykle, można znaleźć w zoo .$\mathsf{BPTIME}(n^c) \subseteq \mathsf{BPTIME}(n)$$c > 1$$\mathsf{BPTIME}$$O(\log n)$

Związek z derandomizacją pochodzi z wyników Impagliazza i Wigdersona: wykazali oni, że przy założeniu prawdopodobnej złożoności dla dowolnego stałego i pewnego stałego . Klasyczne twierdzenia dotyczące hierarchii czasu dla czasu deterministycznego implikują hierarchię czasu dla czasu probabilistycznego. Zadaje odwrotne pytanie: czy hierarchia probabilistyczna uderza w barierę związaną z udowodnieniem wyników derandomizacji?$\mathsf{BPTIME}(n^d) \subseteq \mathsf{DTIME}(n^c)$$d$$c$

Jeśli ktoś ma spostrzeżenia na temat tego, co stoi między nami i dowodzi, że istnieje hierarchia czasu probabilistycznego, prosimy o odpowiedź / komentarz. Oczywiście oczywistą odpowiedzią jest to, że ma semantyczną definicję, która sprzeciwia się klasycznym technikom. Interesują mnie mniej oczywiste obserwacje.$\mathsf{BPTIME}$

Niech PTH będzie hipotezą, że istnieje probabilistyczna hierarchia czasu. Załóżmy, że odpowiedź na twoje pytanie jest prawdziwa, tzn. „PTH oznacza ” dla niektórych stałych c . Wtedy E X P ≠ B P P byłoby bezwarunkowo prawdziwe. Rozważ dwa przypadki:$BPP \subseteq TIME[2^{n^{c}}]$$c$$EXP \neq BPP$

• Jeśli PTH jest fałszywe, a następnie . To jest przeciwieństwo tego, co zauważył Lance.$EXP \neq BPP$
• Jeśli PTH jest prawdziwy, wówczas "PTH oznacza ", więc jeszcze raz E X P ≠ B P P .$BPP \subseteq TIME[2^{n^{c}}]$$EXP \neq BPP$

W rzeczywistości nawet nieskończenie często derandomizacja BPP pod PTH pociągałaby za sobą bezwarunkowo Niezależnie od tego, jakie bariery dotyczą dowodzenia E X P ≠ B P P , odnoszą się one do stwierdzeń typu „PTH implikuje derandomizację”.$EXP \neq BPP$$EXP \neq BPP$

Wyznaczenie probabilistycznej hierarchii czasu nie jest trudne, jeśli BPP = EXP, skrajny przypadek braku derandomizacji.