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 tels qu'il existe un polynôme et un langage vérifiants que pour tout mot  :

  • .
  • .

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 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 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 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 et 1/3 par (pour tout 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, , 432 p. (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, (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,‎ , p. 675-695