BPP (complexité)

Pour les articles homonymes, voir BPP.

En informatique théorique, plus précisément en théorie de la complexité, la classe BPP (bounded-error probabilistic polynomial time) est la classe de problèmes de décision décidés par une machine de Turing probabiliste en temps polynomial, avec une probabilité d'erreur dans la réponse inférieure à 1/3.

Définition[modifier | modifier le code]

Première définition[modifier | modifier le code]

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.

Définition formelle[modifier | modifier le code]

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}}}$.

Relations avec les autres classes[modifier | modifier le code]

Temps polynomial déterministe versus probabiliste[modifier | modifier le code]

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

Autres relations[modifier | modifier le code]

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.

Propriétés et théorèmes[modifier | modifier le code]

• On peut avoir des machines plus efficaces si nécessaire, autrement dit on peut remplacer 2/3 par ${\displaystyle 1-\epsilon }$ et 1/3 par ${\displaystyle \epsilon }$ (pour tout ${\displaystyle \epsilon }$ petit), en ne changeant pas la classe. Ce renforcement peut être effectué en lançant plusieurs fois la machine de façon indépendante et en faisant un vote. Le calcul utilise les bornes de Chernoff.

• BPP est close par complémentaire, i.e. BPP = co-BPP.
• BPP n'a pas de problème complet connu, il faut passer aux problèmes à promesse (PromiseBPP).

Histoire[modifier | modifier le code]

Cette classe a été introduite par J. Gill^[3] dans l'article Computational complexity of probabilistic Turing machines, en même temps que les classes RP et ZPP^[4].

Bibliographie[modifier | modifier le code]

• (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 7 (« Randomized Computation »)
• Leonard. M. Adleman, « Two theorems on random polynomial time », dans Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science, 1978, 75–83 p. (DOI 10.1109/SFCS.1978.37)

Lien externe[modifier | modifier le code]

• (en) La classe BPP sur le Complexity Zoo

Notes et références[modifier | modifier le code]

• Portail de l'informatique théorique