Para um oráculo aleatório R, BPP é igual ao conjunto de linguagens computáveis ​​em P ^ R?

Bem, o título praticamente diz tudo. A pergunta interessante acima foi feita pelo comentarista Jay no meu blog (veja aqui e aqui ). Suponho que a resposta é sim e que existe uma prova relativamente simples, mas não a vi de imediato. (Muito grosso modo, pode-se tentar mostrar que, se um idioma em não estivesse em B P P , então ele deve ter informações mútuas algorítmicas infinitas com R , caso em que não seria computável. essa direção é trivial: as linguagens computáveis ​​em P R certamente contêm B P P. )$P^R$$BPP$$R$$P^R$ $BPP$

Note que estou não perguntando sobre a classe AlmostP , que consiste dessas línguas que estão em para quase todos os R (e é bem conhecido para igualar B P P ). Nesta questão, primeiro fix R , em seguida olhar para o conjunto de idiomas computáveis em P R . Por outro lado, pode-se tentar mostrar que, se um idioma em P R é calculável, mesmo para uma fixa a Oracle aleatório R , então, de facto, que a língua devem ser em uma l m o s t P .$P^R$$R$$BPP$$R$$P^R$$P^R$$R$$AlmostP$

Uma questão intimamente relacionada é se, com probabilidade 1 sobre um oráculo aleatório , temos$R$

$AM = NP^R \cap Computable.$

Nesse caso, obtemos a seguinte conseqüência interessante: se , com probabilidade 1 sobre um oráculo aleatório R , os únicos idiomas que testemunham a separação do oráculo P R ≠ N P R são idiomas incontestáveis.$P=NP$$R$$P^R \ne NP^R$

Sim.

Em primeiro lugar, uma vez que me levou um minuto para descobrir isso sozinho, deixe-me formalizar a diferença entre a sua pergunta e ; é a ordem dos quantificadores. A l m o s t P : = { L : P r R ( L ∈ P R ) = 1 } , e o resultado que você alude é ∀ $\mathsf{AlmostP}$$\mathsf{AlmostP} := \{L : Pr_R(L \in \mathsf{P}^R) = 1\}$$\forall L\, L \in \mathsf{BPP} \iff Pr_R(L \in \mathsf{P}^R) = 1$ . Se entendi corretamente, você está perguntando se .$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})$

Pelo limite da união, o é delimitado por ∑ L ∈ C O M P P r R ( L ∈ P R ∖ B P P ) . (Observe que a última soma é contável.) Agora, pela lei 0-1 - que se aplica, pois todas as declarações relevantes não mudam se mudarmos R finitamente - cada probabilidade individual nessa soma é 0 ou 1. Se a a resposta à sua pergunta é não, então p = 1 , então deve haver algum 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}$ . Mas isso contraria o facto de Um l m o s t P = B P P .$Pr_R(L \in \mathsf{P}^R \backslash \mathsf{BPP}) = 1$$\mathsf{AlmostP} = \mathsf{BPP}$

Actualizar 10 de outubro de 2014 : Como foi salientado no comentário por Emil Jerabek, o mesmo se aplica a vs. N P R , uma vez que também sabe que um l m o s t N P = A M .$\mathsf{AM}$$\mathsf{NP}^R$$\mathsf{AlmostNP} = \mathsf{AM}$

Ele também ressalta que não usamos nada sobre além de que é uma classe contável que contém B P P (resp., A M ). Portanto, a "conclusão interessante" no OQ realmente se aplica a qualquer classe contável de linguagens C que contém A M : se P = N P , as "únicas" linguagens que testemunham a separação do oráculo P R ≠ N P R estão fora de $\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\}$, and thereby "show" that no $L_0$ realizes $\mathsf{NP}^R \neq \mathsf{P}^R$, contradicting the well-known theorem). Rather, writing it out symbolically, we've shown:

If $\mathsf{P} = \mathsf{NP}$, then $\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$.

Note that, crucially, probability 1 is not the same thing as all $R$, and which full-measure set of $R$ satisfy the argument to $Pr_R$ can depend on $\mathcal{C}$. So if we try to alter $\mathcal{C}$ to $\mathcal{C} \cup \{L_0\}$, it at most removes a measure 0 set of $R$ that satisfy this statement.

Embora a ordem dos quantificadores entre o que você está perguntando e quase P seja diferente, não é muito difícil mostrar que eles são equivalentes. Primeiro, para qualquer L fixo, a questão de saber se L \ em P ^ O não depende de nenhum segmento inicial finito de O. segue-se que a probabilidade de L \ em P ^ R ser 0 ou 1. Do quase - P resulta que, para cada L computável que não esteja no BPP, a resposta é 0, enquanto que se L \ no BPP, a probabilidade é 1. Como existem muitos L computáveis, podemos fazer um vínculo de união; uma união contável de conjuntos de probabilidade 0 tem probabilidade 0. Portanto, a probabilidade de que haja qualquer L computável que não esteja no BPP, mas esteja em P ^ R é 0, assim como a probabilidade de que exista um idioma no BPP que não esteja em P ^ R,