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.

Relation with other complexity classes

Larger complexity classes

Complexity class	Meaning	Proof of containment	Reverse containment -- separation result or open problem	Intermediate complexity classes
RP (randomized polynomial time)	Unlike ZPP, there is no definitive No answer type here but only a Yes and a Maybe			click here
co-RP	Unlike ZPP, there is no definitive Yes answer type here but only a No and a Maybe			click here
BPP (bounded-error probabilistic polynomial time)	There are only maybe yes and maybe no answers, no definitive answers, but bounds on error rates			click here
PP (probabilistic polynomial time)	Like BPP, weaker bounds on error rates			click here
NP intersect co-NP				click here
NP
co-NP

Smaller complexity classes

Complexity class	Meaning	Proof of containment	Reverse containment -- separation result or open problem	Intermediate complexity classes
P