BPP (complexité)

La classe BPP est l'ensemble des problèmes, ou de façon équivalente des langages, pour lesquels il existe une machine de Turing probabiliste en temps polynomial qui satisfait les conditions d'acceptation suivantes :

• Si le mot n'est pas dans le langage, la machine le rejette avec une probabilité supérieure à 2/3.
• Si le mot est dans le langage, la machine l'accepte avec une probabilité supérieure à 2/3.

Autrement dit la machine se trompe avec une probabilité inférieure à 1/3.

On définit la classe BPP comme l'ensemble des langages ${\displaystyle L}$ tels qu'il existe un polynôme ${\displaystyle p(n)}$ et un langage ${\displaystyle A\in {\rm {P}}}$ vérifiants que pour tout mot ${\displaystyle x}$ :

• ${\displaystyle x\in L\Rightarrow {\underset {\varepsilon \in \{0,1\}^{p(|x|)}}{Pr}}((x,\varepsilon )\in A)\geq {\frac {2}{3}}}$.
• ${\displaystyle x\notin L\Rightarrow {\underset {\varepsilon \in \{0,1\}^{p(|x|)}}{Pr}}((x,\varepsilon )\in A)\leq {\frac {1}{3}}}$.

On peut utiliser une machine probabiliste pour faire un calcul déterministe, et donc P ${\displaystyle \scriptstyle \subseteq }$ BPP. L'autre inclusion est une question ouverte. En terme plus généraux, la question est de savoir si l'aléatoire est utile pour accélérer le calcul ou non. Il y a eu à ce sujet un changement d'avis de la part de la communauté de la complexité : jusqu'aux années 80, la plupart des chercheurs pensaient que BPP était différente de P, puis divers résultats ont bousculé cette croyance. Aujourd'hui une égalité est souvent envisagée[1].

Inclusions de classes de complexité probabilistes.

BPP contient aussi les classes probabilistes dont les conditions d'acceptation sont plus fortes ZPP, RP et co-RP.

Avec les notations de la hiérarchie polynomiale, on a ${\displaystyle BPP\subseteq \Sigma _{2}^{p}\cap \Pi _{2}^{p}}$ d'après le théorème de Sipser–Gács–Lautemann[2].

Dans le monde des classes de circuits booléens, le théorème d'Adleman donne BPP ${\displaystyle \scriptstyle \subseteq }$ P/poly (Adleman 1978).

La variante quantique de BPP est BQP.