Consequências de contendo

34

Muitos acreditam que . No entanto, sabemos apenas que está no segundo nível da hierarquia polinomial, ou seja, . Um passo para mostrar é primeiro reduzi-lo ao primeiro nível da hierarquia polinomial, ou seja, .BPP=PNPBPPBPPΣ2PΠ2PBPP=PBPPNP

A contenção significaria que o não determinismo é pelo menos tão poderoso quanto a aleatoriedade para o tempo polinomial.

Isso também significa que se, para um problema, podemos encontrar as respostas usando algoritmos aleatórios eficientes (tempo polinomial), podemos verificar as respostas com eficiência (em tempo polinomial).

Existem consequências interessantes conhecidas para ?BPPNP

Existem razões para acreditar que provar está fora de alcance agora (por exemplo, barreiras ou outros argumentos)?BPPNP

Kaveh
fonte
3
Bem, acho que não se sabe coRPNP.

Respostas:

37

Por um lado, provar implicaria facilmente que N E X P B P P , o que já significa que sua prova não pode ser relativizada.BPPNPNEXPBPP

Olhar, mas vamos em algo ainda mais fraco: . Se isso for verdade, o teste de identidade polinomial para circuitos aritméticos ocorre em tempo subexponencial não determinístico. Por Impagliazzo-Kabanets'04 , esse algoritmo implica limites inferiores do circuito: ou o Permanente não possui circuitos aritméticos de tamanho médio, ou N E X P P / p o l y .coRPNTIME[2no(1)]NEXPP/poly

Pessoalmente, não sei por que parece "fora de alcance", mas parece difícil de provar. Certamente, alguns truques genuinamente novos serão necessários para provar isso.

Ryan Williams
fonte
12
Um pequeno adendo, se alguém se importa: enquanto Avi e eu não pensamos em fazer isso em nosso artigo, acredito que alguém poderia mostrar facilmente adaptando nossos argumentos (por exemplo, para NEXP vs. P / poly) que qualquer prova de BPP em NP também precisaria ser não-algebrizante.
21413 Scott Schaffner
2
Scott: Não tenho dúvida de que isso também é verdade!
Ryan Williams
@RyanWilliams A barreira das provas naturais também se aplica ao BPP no NP? perguntando isso porque como foi possível superar a barreira (se houver alguma) para mostrar contenção em ? Σ2
T ....
2
Como as propriedades naturais geralmente falam apenas de barreiras contra limites inferiores não uniformes (de circuito), não sei o que eles poderiam dizer sobre se o BPP está contido no NP.
Ryan Williams
VNPVP