Para un oráculo aleatorio R, ¿BPP es igual al conjunto de lenguajes computables en P ^ R?

Bueno, el título lo dice todo. La interesante pregunta anterior fue hecha por el comentarista Jay en mi blog (ver aquí y aquí ). Supongo que la respuesta es sí y que hay una prueba relativamente simple, pero no pude verlo de manera improvisada. (En términos muy generales, sin embargo, se podría tratar de demostrar que, si una lengua en no estaban en B P P , entonces debe tener información mutua algorítmica infinita con R , en cuyo caso no sería computable. Además, la nota esa única dirección es trivial: los lenguajes computables en P R ciertamente contienen B P P ).$P^R$$BPP$$R$$P^R$ $BPP$

Tenga en cuenta que estoy no preguntar sobre la clase AlmostP , que consiste en aquellas lenguas que están en para casi todos los R (y es bien conocido por ser igual a B P P ). En esta pregunta, primer punto de referencia R , y luego mirar el conjunto de idiomas computables en P R . Por otro lado, se podría tratar de demostrar que, si una lengua en P R es computable, incluso para un fijo oráculo aleatorio R , entonces, de hecho de que el lenguaje debe estar en A l m o s t P .$P^R$$R$$BPP$$R$$P^R$$P^R$$R$$AlmostP$

Una pregunta estrechamente relacionada es si, con probabilidad 1 sobre un oráculo aleatorio , tenemos$R$

$AM = NP^R \cap Computable.$

Si es así, obtenemos la siguiente consecuencia interesante: si , entonces, con probabilidad 1 sobre un oráculo aleatorio R , los únicos idiomas que presencian la separación del oráculo P R ≠ N P R son idiomas no calificables.$P=NP$$R$$P^R \ne NP^R$

Si.

Primero, dado que me tomó un minuto darme cuenta de esto, permítanme formalizar la diferencia entre su pregunta y ; Es el orden de los cuantificadores. A l m o s t P : = { L : P r R ( L ∈ P R ) = 1 } , y el resultado al que alude es ∀ $\mathsf{AlmostP}$$\mathsf{AlmostP} := \{L : Pr_R(L \in \mathsf{P}^R) = 1\}$ . Si he entendido correctamente, me preguntas si 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$

Considerar

.$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})$

Por el enlace de unión, la está limitada por ∑ L ∈ C O M P P r R ( L ∈ P R ∖ B P P ) . (Tenga en cuenta que la última suma es contable). Ahora, según la ley 0-1, que se aplica dado que todas las declaraciones relevantes no cambian si cambiamos R de manera finita, cada probabilidad individual en esta suma es 0 o 1. Si el la respuesta a su pregunta es no, entonces p = 1 , por lo que debe haber alguna L ∈ C O M P tal que$p$$\sum_{L \in \mathsf{COMP}} Pr_R(L \in \mathsf{P}^R \backslash \mathsf{BPP})$$R$$p=1$$L \in \mathsf{COMP}$ . Pero esto contradice el hecho de que A l m o s t P = B P P .$Pr_R(L \in \mathsf{P}^R \backslash \mathsf{BPP}) = 1$$\mathsf{AlmostP} = \mathsf{BPP}$

Actualización Oct 10, 2014 : Como se señaló en el comentario por Emil Jeřábek, el mismo argumento se aplica a vs N P R , ya que también sabemos que A l m o s t N P = A M .$\mathsf{AM}$$\mathsf{NP}^R$$\mathsf{AlmostNP} = \mathsf{AM}$

$\mathsf{COMP}$$\mathsf{BPP}$$\mathsf{AM}$$\mathcal{C}$$\mathsf{AM}$$\mathsf{P} = \mathsf{NP}$$\mathsf{P}^R \neq \mathsf{NP}^R$$\mathcal{C}$$L_0$$\mathcal{C} = \mathsf{AM} \cup \{L_0\}$ $L_0$$\mathsf{NP}^R \neq \mathsf{P}^R$

$\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$

$R$$R$$Pr_R$$\mathcal{C}$$\mathcal{C}$$\mathcal{C} \cup \{L_0\}$$R$

Si bien el orden de los cuantificadores entre lo que está preguntando y casi P difiere, no es demasiado difícil demostrar que son equivalentes. Primero, para cualquier L fija, la cuestión de si L \ en P ^ O no depende de ningún segmento inicial finito de O. De esto se deduce que la probabilidad de que L \ en P ^ R sea 0 o 1. De casi - El resultado de P, para cada L computable que no está en BPP, la respuesta es 0, mientras que si L \ en BPP, la probabilidad es 1. Dado que hay muchas L computables, podemos hacer un enlace de unión; una unión contable de conjuntos de probabilidad 0 tiene probabilidad 0. Por lo tanto, la probabilidad de que haya algún L computable que no esté en BPP pero esté en P ^ R es 0, al igual que la probabilidad de que haya un lenguaje en BPP que no esté en P ^ R