ZPP

This article defines a decision complexity class, i.e., a complexity class for decision problems. This means that given any language, the language is either a member of the decision complexity class or it is not a member of the decision complexity class.| View a list of complexity classes

Definition

The zero-error probabilistic polynomial time complexity class, abbreviated ZPP, is defined as follows. A language $L$ is in ZPP if there exists a Turing machine that has access to a random oracle and runs in polynomial time and has one of three outputs: Yes, No, and Undecided. If the output is Yes, the string is in $L$. If the output is No, the string is not in $L$. if the output is Undecided, then the string may or may not be in $L$. Further, for any fixed choice of input string, the probability of returning Maybe is bounded from above by a number strictly less than 1.

This complexity class can also be defined as the intersection of the RP and co-RP complexity classes.