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]

Inclusions de classes de complexité probabilistes

On peut utiliser une machine probabiliste pour faire un "calcul déterministe", et donc P  \scriptstyle \subseteq BPP.

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

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[2] dans l'article Computational complexity of probabilistic Turing machines, en même temps que les classes RP et ZPP[3].

Bibliographie[modifier | modifier le code]

Lien externe[modifier | modifier le code]

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

  1. (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
  2. Complexity Zoo
  3. (en) John Gill, « Computational complexity of probabilistic Turing machines », SIAM Journal on Computing, vol. 6, no 4,‎ 1977, p. 675-695