Consecuencias de

34

Muchos creen que BPP=PNP . Sin embargo, solo sabemos que BPP está en el segundo nivel de jerarquía polinómica, es decir, BPPΣ2PΠ2P . Un paso hacia la muestra BPP=P es a primera bajarla hasta el primer nivel de la jerarquía de polinomio, es decir, BPPNP .

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 ?BPPNP

¿Hay alguna razón para creer que probar está fuera de alcance en este momento (por ejemplo, barreras u otros argumentos)?BPPNP

Kaveh
fuente
3
Bueno, no creo que se sepa que coRPNP.

Respuestas:

37

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.BPPNPNEXPBPP

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 .coRPNTIME[2no(1)]NEXPP/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.

Ryan Williams
fuente
12
Un pequeño apéndice, si a alguien le importa: aunque Avi y yo no pensamos hacer esto en nuestro documento, creo que uno podría mostrar fácilmente adaptando nuestros argumentos (por ejemplo, para NEXP vs. P / poly) que cualquier prueba de BPP en NP también debería ser no algebrizante.
Scott Aaronson el
2
Scott: ¡No tengo dudas de que eso también es cierto!
Ryan Williams el
@RyanWilliams ¿La barrera de pruebas naturales también se aplica para BPP en NP? preguntando esto porque ¿cómo fue posible superar la barrera (si es que la hubo) para mostrar contención en ? Σ2
T ....
2
Dado que las propiedades naturales generalmente solo hablan de barreras contra los límites inferiores no uniformes (circuito), no sé qué podrían decir acerca de si BPP está contenido en NP.
Ryan Williams
@RyanWilliams es 'Permanente no tiene circuitos aritméticos de tamaño polivinílico' igual que o ¿es más débil? VNPVP
T ....