Czy dla losowej wyroczni R BPP równa się zestawowi języków obliczeniowych w P ^ R?

Cóż, tytuł prawie wszystko mówi. Interesujące pytanie powyżej zostało zadane przez komentatora Jaya na moim blogu (patrz tutaj i tutaj ). Zgaduję, że odpowiedź brzmi „tak” i że istnieje stosunkowo prosty dowód, ale nie widziałem go od razu. (Jednak z grubsza można by próbować pokazać, że jeśli język w nie był w , to musiałby mieć nieskończoną algorytmiczną wzajemną informację z , w którym to przypadku nie byłby obliczalny. Należy również pamiętać, że jeden kierunek jest trywialny: języki obliczeniowe w pewnością zawierają ).$P^R$$BPP$$R$$P^R$ $BPP$

Zauważ, że nie pytam o klasę AlmostP , która składa się z tych języków, które są w dla prawie każdego (i jest dobrze znane z równego ). Na to pytanie, musimy najpierw naprawić , a następnie spojrzeć na zestaw języków obliczalnych w . Z drugiej strony, może próbować pokazują, że gdy język, w jest obliczeniowy, nawet na nieruchomej losowo oracle , to w rzeczywistości, że język musi znajdować się w A l m O a T P .$P^R$$R$$BPP$$R$$P^R$$P^R$$R$$AlmostP$

Ściśle powiązane pytanie brzmi, czy z prawdopodobieństwem 1 w stosunku do losowej wyroczni$R$ mamy

$AM = NP^R \cap Computable.$

Jeśli tak, to otrzymujemy następującą interesującą konsekwencję: jeśli , to z prawdopodobieństwem 1 przypadkowej wyroczni R , jedynymi językami, które są świadkami separacji wyroczni P R ≠ N P R, są języki nieobliczalne.$P=NP$$R$$P^R \ne NP^R$

Tak.

Po pierwsze, ponieważ zajęło mi chwilę, aby dowiedzieć się tego ja, niech mi sformalizować różnicę między pytaniem a ; jest to kolejność kwantyfikatorów. A l m o s t P : = { L : P r R ( L ∈ P R ) = 1 } , a wynikiem, o którym wspominasz, jest ∀ $\mathsf{AlmostP}$$\mathsf{AlmostP} := \{L : Pr_R(L \in \mathsf{P}^R) = 1\}$ . Jeśli dobrze zrozumiałem, pytasz, czy P r R ( ∀ $\forall L\, L \in \mathsf{BPP} \iff Pr_R(L \in \mathsf{P}^R) = 1$ .$Pr_R(\forall L\, L \in \mathsf{P}^R \cap \mathsf{COMP} \iff L \in \mathsf{BPP}) = Pr_R(\mathsf{P}^R \cap \mathsf{COMP} = \mathsf{BPP}) = 1$

Rozważać

.$p := 1-Pr_R(\mathsf{P}^R\cap \mathsf{COMP} = \mathsf{BPP}) = Pr_R(\exists L \in \mathsf{P}^R \cap \mathsf{COMP} \backslash \mathsf{BPP})$

W związku związkowym jest ograniczone górną granicą przez ∑ L ∈ C O M P P r R ( L ∈ P R ∖ B P P ) . (Zauważ, że ta ostatnia suma jest policzalna.) Teraz, zgodnie z prawem 0-1 - które ma zastosowanie, ponieważ wszystkie odpowiednie stwierdzenia nie zmieniają się, jeśli ostatecznie zmienimy R - każde prawdopodobieństwo w tej sumie wynosi 0 lub 1. Jeśli odpowiedź na twoje pytanie brzmi: nie, to p = 1 , więc musi być trochę L ∈ C O M P, takich jak$p$$\sum_{L \in \mathsf{COMP}} Pr_R(L \in \mathsf{P}^R \backslash \mathsf{BPP})$$R$$p=1$$L \in \mathsf{COMP}$ . Lecz to fakt, że l m O a T P = B P P .$Pr_R(L \in \mathsf{P}^R \backslash \mathsf{BPP}) = 1$$\mathsf{AlmostP} = \mathsf{BPP}$

Aktualizacja 10 październik 2014 : Jak wskazano w komentarzu Emil Jeřábek, to samo odnosi się do argumentu wobec N P R , ponieważ również, że l m O a T N P = M .$\mathsf{AM}$$\mathsf{NP}^R$$\mathsf{AlmostNP} = \mathsf{AM}$

Wskazuje również, że nie używaliśmy niczego o poza tym, że jest to klasa policzalna, która zawiera B P P (odpowiednio, A M ). Więc „interesujący wniosek” w OQ rzeczywiście odnosi się do dowolnej policzalnych klasy języków C , który zawiera A M : jeśli P = N P , to „tylko” Języki, w których świadek separacja wyrocznia P R ≠ N P R są poza $\mathsf{COMP}$$\mathsf{BPP}$$\mathsf{AM}$$\mathcal{C}$$\mathsf{AM}$$\mathsf{P} = \mathsf{NP}$$\mathsf{P}^R \neq \mathsf{NP}^R$$\mathcal{C}$. Ale to ostatnie stwierdzenie wydaje mi się nieco mylące (wydaje się, że dla każdego możemy rozważyć C = A M ∪ { L 0 } , a tym samym „pokazać”, że żaden L 0 nie realizuje N P R ≠ P R , sprzeczne ze znanym twierdzeniem). Raczej pisząc to symbolicznie, pokazaliśmy:$L_0$$\mathcal{C} = \mathsf{AM} \cup \{L_0\}$ $L_0$$\mathsf{NP}^R \neq \mathsf{P}^R$

Jeśli , to ∀ policzalne  C ⊇ A $\mathsf{P} = \mathsf{NP}$ .$\forall \text{countable } \mathcal{C} \supseteq \mathsf{AM}\, Pr_R(\mathsf{NP}^R \neq \mathsf{P}^R \text{ and } \mathsf{NP}^R \cap \mathcal{C} = \mathsf{P}^R \cap \mathcal{C}) = 1$

Należy zauważyć, że ważne, prawdopodobieństwo 1 nie jest to to samo, co wszystkich i które pełnej środek zestaw R spełniałby argumentem P r R może zależeć od C . Więc jeśli spróbujemy zmienić C na C ∪ { L 0 } , to co najwyżej usunie zestaw R miary 0, który spełnia tę instrukcję.$R$$R$$Pr_R$$\mathcal{C}$$\mathcal{C}$$\mathcal{C} \cup \{L_0\}$$R$

Chociaż kolejność kwantyfikatorów między pytaniem a prawie P jest różna, nietrudno jest wykazać, że są one równoważne. Po pierwsze, dla każdego ustalonego L pytanie, czy L \ w P ^ O nie zależy od żadnego skończonego początkowego segmentu O. Wynika z tego, że prawdopodobieństwo, że L \ w P ^ R wynosi 0 lub 1. Z prawie - Wynik P, dla każdego obliczalnego L spoza BPP, odpowiedź wynosi 0, natomiast jeśli L \ w BPP, prawdopodobieństwo wynosi 1. Ponieważ istnieje obliczalnie wiele obliczalnych L, możemy wykonać związanie związane; policzalna suma zbiorów prawdopodobieństwa 0 ma prawdopodobieństwo 0. Zatem prawdopodobieństwo, że istnieje jakikolwiek obliczalny L, który nie jest w BPP, ale jest w P ^ R wynosi 0, podobnie jak prawdopodobieństwo, że istnieje język w BPP nie w P ^ R,