Conséquences de

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 P ⊆ N P .$\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$$\mathsf{BPP}$$\mathsf{BPP}\subseteq \Sigma^ \mathsf{P}_2 \cap \Pi^ \mathsf{P}_2$$\mathsf{BPP} = \mathsf{P}$$\mathsf{BPP} \subseteq \mathsf{NP}$

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 ?$\mathsf{BPP} \subseteq \mathsf{NP}$

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)?$\mathsf{BPP} \subseteq \mathsf{NP}$

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.$BPP \subseteq NP$$NEXP \neq BPP$

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 .$coRP \subseteq NTIME[2^{n^{o(1)}}]$$NEXP \not\subset P/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.