Consecuencias de

Muchos creen que $\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$ . Sin embargo, solo sabemos que $\mathsf{BPP}$ está en el segundo nivel de jerarquía polinómica, es decir, $\mathsf{BPP}\subseteq \Sigma^ \mathsf{P}_2 \cap \Pi^ \mathsf{P}_2$ . Un paso hacia la muestra $\mathsf{BPP} = \mathsf{P}$ es a primera bajarla hasta el primer nivel de la jerarquía de polinomio, es decir, $\mathsf{BPP} \subseteq \mathsf{NP}$ .

La contención significaría que el no determinismo es al menos tan poderoso como la aleatoriedad para el tiempo polinomial.

También significa que si para un problema podemos encontrar las respuestas utilizando algoritmos aleatorizados eficientes (tiempo polinómico), entonces podemos verificar las respuestas de manera eficiente (en tiempo polinómico).

¿Hay alguna consecuencia interesante conocida para ?$\mathsf{BPP} \subseteq \mathsf{NP}$

¿Hay alguna razón para creer que probar está fuera de alcance en este momento (por ejemplo, barreras u otros argumentos)?$\mathsf{BPP} \subseteq \mathsf{NP}$

Por un lado, probar implicaría fácilmente que N E X P ≠ B P P , lo que ya significa que su prueba no puede relativizarse.$BPP \subseteq NP$$NEXP \neq BPP$

Pero veamos algo aún más débil: . Si eso es cierto, entonces la prueba de identidad polinómica para circuitos aritméticos se realiza en tiempo subexponencial no determinista. Según Impagliazzo-Kabanets'04 , dicho algoritmo implica límites inferiores del circuito: o el permanente no tiene circuitos aritméticos de polietileno, o N E X P ⊄ P / p o l y .$coRP \subseteq NTIME[2^{n^{o(1)}}]$$NEXP \not\subset P/poly$

Personalmente, no sé por qué parece "fuera de alcance", pero parece difícil de probar. Ciertamente, se necesitarán algunos trucos genuinamente nuevos para probarlo.