BPP (complexité)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La classe BPP, est un objet de la théorie de la complexité, en informatique théorique. C'est une classe de problèmes de décision qui peut-être définie avec des machines de Turing probabilistes. L'acronyme BPP vient de Bounded-error Probabilistic Polynomial time.

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 un probabilité inférieure à 1/3.

Définition formelle[modifier | modifier le code]

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

  • x \in L \Rightarrow \underset{\varepsilon\in \{0,1\}^{p(|x|)}}{Pr}((x,\varepsilon)\in A) \ge \frac{2}{3} .
  • x \notin L \Rightarrow \underset{\varepsilon\in \{0,1\}^{p(|x|)}}{Pr}((x,\varepsilon)\in A) \le \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  \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]

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 BPP \subseteq \Sigma^p_2 \cap \Pi^p_2 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 \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, autrementdit on peut remplacer 2/3 par 1-\epsilon et 1/3 par \epsilon (pour tout \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.

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]

Lien externe[modifier | modifier le code]

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

  1. Sylvain Perifel, Complexité algorithmique, Ellipses,‎ 2014 (ISBN 9782729886929, lire en ligne), chap. 12.1 (« Dérandomisation ») p. 318.
  2. (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A modern Approach, Cambridge University Press,‎ 2009 (ISBN 0-521-42426-7), chap. 7 section 5.2 BPP is in PH
  3. Complexity Zoo
  4. (en) John Gill, « Computational complexity of probabilistic Turing machines », SIAM Journal on Computing, vol. 6, no 4,‎ 1977, p. 675-695