Voir la source de BPP (complexité)

{{Voir homonymes|BPP}}

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

== Définition ==

=== Première définition ===

La classe BPP est l'ensemble des problèmes, ou de façon équivalente des [[langage formel|langages]], pour lesquels il existe une [[machine de Turing probabiliste]] en temps [[polynôme|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 ===
On définit la classe '''BPP''' comme l'ensemble des langages <math>L</math> tels qu'il existe un polynôme <math>p(n)</math> et un langage <math>A \in {\rm P} </math> vérifiant que pour tout mot <math>x</math> : 
* <math>x \in L \Rightarrow \underset{\varepsilon\in \{0,1\}^{p(|x|)}}{Pr}((x,\varepsilon)\in A) \ge \frac{2}{3} </math>.
* <math>x \notin L \Rightarrow \underset{\varepsilon\in \{0,1\}^{p(|x|)}}{Pr}((x,\varepsilon)\in A) \le \frac{1}{3}</math>.

== Relations avec les autres classes ==
=== Temps polynomial déterministe versus probabiliste ===
On peut utiliser une machine probabiliste pour faire un calcul déterministe, et donc '''[[P (complexité)|P]]''' <math> \scriptstyle \subseteq</math> '''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<ref>{{Complexité algorithmique (Perifel)|titre chapitre= Dérandomisation|numéro chapitre=12.1}} p. 318.</ref>.

=== Autres relations ===
[[Fichier:Randomized Complexity Classes.svg|thumb|Inclusions de classes de complexité probabilistes.]]
BPP contient aussi les classes probabilistes dont les conditions d'acceptation sont plus fortes '''[[ZPP (complexité)|ZPP]]''', '''[[RP (complexité)|RP et co-RP]]'''.

Avec les notations de la [[hiérarchie polynomiale]], on a <math>BPP \subseteq \Sigma^p_2 \cap \Pi^p_2</math>  d'après le [[théorème de Sipser–Gács–Lautemann]]<ref>{{Computational Complexity (Arora et Barak)|numéro chapitre=7}} section 5.2 ''BPP is in PH''</ref>.

Dans le monde des classes de [[circuit booléen|circuits booléens]], le théorème d'[[Leonard Adleman|Adleman]] donne '''BPP''' <math>\scriptstyle \subseteq</math> '''[[P/poly]]''' {{harv|Adleman|1978}}.

La variante quantique de '''BPP''' est '''[[BQP]]'''.

==Propriétés et théorèmes==

*On peut avoir des machines plus efficaces si nécessaire, autrement dit  on peut remplacer 2/3 par <math>1-\epsilon </math>  et 1/3 par <math>\epsilon</math> (pour tout <math>\epsilon </math> 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ème à promesse|problèmes à promesse]] (PromiseBPP).

==Histoire==
Cette classe a été introduite par J. Gill<ref>[https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R Complexity Zoo]</ref> dans l'article ''Computational complexity of probabilistic Turing machines'', en même temps que les classes [[RP (complexité)|RP]] et [[ZPP (complexité)|ZPP]]<ref> 
{{Article
 | langue                 =  en
 | prénom1                = John
 | nom1                   = Gill
 | lien auteur1           = 
 | titre                  = Computational complexity of probabilistic Turing machines
 | périodique             = SIAM Journal on Computing
 | lien périodique        =  
 | volume                 = 6
 | numéro                 = 4
 | jour                   = 
 | mois                   = 
 | année                  = 1977
 | pages                  = 675-695
 | issn                   = 
 | url texte              = 
 | consulté le            = 
 | id                     = 
}}</ref>.

==Bibliographie==
* {{Computational Complexity (Arora et Barak)|numéro chapitre=7|titre chapitre=Randomized Computation}}
* {{chapitre
 | nom1 = Adleman 
 | prénom1 = Leonard. M. 
 | lien auteur1 = Leonard Adleman
 | titre chapitre = Two theorems on random polynomial time
 | doi = 10.1109/SFCS.1978.37
 | pages = 75–83
 | titre ouvrage = Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science
 | année = 1978}}

==Lien externe==
*{{Complexity Zoo|fin=B#bpp|nom=BPP}}

==Notes et références==
<references />

{{Palette|Théorie de la complexité}}

{{Portail|informatique théorique}}

[[Catégorie:Classe de complexité]]