Conséquences de

34

Beaucoup pensent que . Cependant, nous savons seulement que est dans le deuxième niveau de la hiérarchie polynomiale, c'est-à-dire . Un pas vers montrant B P P = P est d'abord de faire descendre au premier niveau de la hiérarchie polynomiale, soit B P PN P .BPP=PNPBPPBPPΣ2PΠ2PBPP=PBPPNP

Le confinement signifierait que le non-déterminisme est au moins aussi puissant que le hasard pour le temps polynomial.

Cela signifie également que si pour un problème, nous pouvons trouver les réponses en utilisant des algorithmes efficaces randomisés (temps polynomial), nous pourrons alors vérifier les réponses efficacement (en temps polynomial).

Existe-t-il des conséquences intéressantes connues pour ?BPPNP

Y a-t-il des raisons de croire que prouver est hors de portée pour le moment (par exemple, des barrières ou d'autres arguments)?BPPNP

Kaveh
la source
3
Eh bien, je ne pense pas qu'on sache que coRPNP.

Réponses:

37

Pour commencer, prouver impliquerait facilement que N E X P B P P , ce qui signifie déjà que votre preuve ne peut pas relativiser.BPPNPNEXPBPP

Mais regardons quelque chose d'encore plus faible: . Si cela est vrai, le test d'identité polynomiale pour les circuits arithmétiques est en temps sous-exponentiel non déterministe. Par Impagliazzo-Kabanets'04 , un tel algorithme implique des bornes inférieures de circuit: soit le permanent ne possède pas de circuits arithmétiques poly-size, ou N E X P P / p o l y .coRPNTIME[2no(1)]NEXPP/poly

Personnellement, je ne sais pas pourquoi cela semble "hors de portée", mais cela semble difficile à prouver. Il faudra certainement de nouvelles astuces pour le prouver.

Ryan Williams
la source
12
Un petit addendum, si ça ne dérange pas: si Avi et moi-même ne pensions pas le faire dans notre article, je pense que nous pourrions assez facilement montrer en adaptant nos arguments (par exemple, pour NEXP contre P / poly) que toute preuve de BPP dans NP devrait également être non algébrique.
Scott Aaronson
2
Scott: Je ne doute pas que c'est aussi vrai!
Ryan Williams
Σ2
2
Comme les propriétés naturelles ne parlent généralement que de barrières contre les limites inférieures non uniformes (circuits), je ne sais pas ce qu’elles pourraient dire sur le fait que la BPP soit contenue dans NP.
Ryan Williams
@RyanWilliams est 'Permanent n'a pas de circuits arithmétiques de tailles multiples' identique à VNPVP or is it weaker?
T....