PP (complexité)
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 (Toda 1991).
PP est close par union et intersection (Beigel, Reingold et Spielman 1991).
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 1977[1] dans l'article Computational complexity of probabilistic Turing machines, en même temps que les classes BPP, RP et ZPP (Gill 1977).
La clôture par différence symétrique de la classe avait été démontrée par David Russo dans sa thèse[2], 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[3].
La relation entre PP et la hiérarchie polynomiale a valu le prix Gödel 1998 à Seinosuke Toda[4].
Notes et références
Bibliographie
- Seinosuke Toda, « PP is as hard as the polynomial-time hierarchy », SIAM Journal on Computing, vol. 20, no 5, , p. 865–877 (DOI 10.1137/0220053, lire en ligne)
- (en) John Gill, « Computational complexity of probabilistic Turing machines », SIAM Journal on Computing, vol. 6, no 4, , p. 675-695
- David Russo, Structural Properties Of Complexity Classes (Ph.D Thesis), University of California, Santa Barbara,
- Richard Beigel, Nick Reingold et Daniel A. Spielman, « PP Is Closed Under Intersection », dans STOC, , p. 1-9
