BPP (complexité)

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. 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. 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 : 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. thumb|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. Dans le monde des classes de circuits booléens, le théorème d'Adleman donne BPP P/poly . La variante quantique de BPP est BQP. 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.