PP est un objet de la théorie de la complexité, un domaine de l'informatique théorique. C'est une classe de complexité probabiliste. Plus précisément c'est l'ensemble de problèmes de décision décidés par une machine de Turing probabiliste en temps polynomial avec une probabilité d'erreur inférieure à un demi.
Définition formelle Un langage L est dans PP s'il existe une machine de Turing probabiliste M, telle que : M fini en temps polynomial sur toutes les instances Pour tout mot x de L, M accepte avec une probabilité strictement plus grande que 1/2 Pour tous les mots qui ne sont pas dans L, M rejette avec une probabilité plus grande que 1/2.
Différence avec la classe BPP Les classes BPP et PP sont très proches au niveau de la définition mais a priori ne sont pas égales. En effet BPP est la classe des problèmes qui peuvent être décidés par une machine en temps polynomial avec une probabilité de bonne réponse supérieure à une constante elle-même strictement plus grande que 1/2. BPP est donc incluse dans PP.
Propriétés
On a les deux inclusions suivantes : NP est incluse dans PP qui est incluse dans PSPACE.
Le théorème de Toda indique que P oracle PP contient PH, la hiérarchie polynomiale .
PP est close par union et intersection .
PP possède des problèmes complets, par exemple MAJSAT : pour une formule F, la machine doit accepter si et seulement si F est vraie pour plus de la moitié des assignations possibles pour les variables.
Histoire Cette classe a été introduite par J. Gill en 1977Complexity Zoo dans l'article Computational complexity of probabilistic Turing machines, en même temps que les classes BPP, RP et ZPP .
La clôture par différence symétrique de la classe avait été démontrée par David Russo dans sa thèse, et la clôture par union et intersection a été démontrée en 1991 après avoir été un problème ouvert pendant 14 ans.
La relation entre PP et la hiérarchie polynomiale a valu le prix Gödel 1998 à Seinosuke Toda.
Notes et références
Bibliographie
Liens externes
Catégorie:Classe de complexité