Loading AI tools
De Wikipédia, l'encyclopédie libre
La classe ZPP, est un objet de la théorie de la complexité, en informatique théorique. C'est une classe de problèmes de décision sur machine de Turing probabiliste. L'acronyme ZPP vient de Zero-Error Probabilistic Polynomial time.
Il existe plusieurs définitions équivalentes de ZPP. On commence par celle qui lui donne son nom.
La classe ZPP est l'ensemble des problèmes, ou de façon équivalentes des langages, pour lesquels il existe une machine de Turing probabiliste telle que :
ZPP est la classe des problèmes qui peuvent être résolus sur une machine de Turing probabiliste en temps polynomial ayant les propriétés suivantes :
La probabilité 1/2 peut de manière équivalente être remplacée par n'importe quel nombre compris entre 0 et 1 strictement.
La classe ZPP est aussi l'intersection des classes RP et co-RP :
Par définition : .
Et on a aussi : P .
Cette classe a été introduite par J. Gill[1] dans l'article Computational complexity of probabilistic Turing machines, en même temps que la classe RP[2].
(en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 7
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.