Loading AI tools
complexité De Wikipédia, l'encyclopédie libre
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.
Un langage L est dans PP s'il existe une machine de Turing probabiliste M, telle que :
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.
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.
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].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.