In complexity theory, ZPP (Zero-error Probabilistic Polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: In computer science, computational complexity theory is the branch of the theory of computation that studies the resources, or cost, of the computation required to solve a given problem. ... In computational complexity theory, Polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ... In computational complexity theory, a complexity class is a set of problems of related complexity. ... In computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which randomly chooses between the available transitions at each point with equal probability. ...

• It always returns the correct YES or NO answer.
• The running time is unbounded, but is polynomial on average for any input.

In other words, the algorithm is allowed to flip a truly-random coin while it's running. It always returns the correct answer. (Such an algorithm is called a Las Vegas algorithm.) For a problem of size n, there is some polynomial p(n) such that the average running time will be less than p(n), even though it might occasionally be much longer. In computing, a Las Vegas algorithm is a randomized algorithm which is correct; that is, it always produces the correct result. ...

Alternatively, ZPP can be defined as the class of problems for which a probabilistic Turing machine exists with these properties: An artistic representation of a Turing Machine . ...

• It always runs in polynomial time.
• It returns an answer YES, NO or DO NOT KNOW.
• The answer is always either DO NOT KNOW or the correct answer.
• If the correct answer is YES, then it returns YES with probability at least 1/2.
• If the correct answer is NO, then it returns NO with probability at least 1/2.

The two definitions are equivalent.

The definition of ZPP is based on probabilistic Turing machines. Other complexity classes based on them include BPP and RP. The class BQP is based on another machine with randomness: the quantum computer. This article is about the complexity class. ... This article relates to the theory of computation. ... BQP, in computational complexity theory, stands for Bounded error, Quantum, Polynomial time. It denotes the class of problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/4 for all instances. ... Molecule of alanine used in NMR implementation of error correction. ...

Intersection definition

The class ZPP is exactly equal to the intersection of the classes RP and Co-RP. This is often taken to be the definition of ZPP. To show this, first note that every problem which is in both RP and co-RP has a Las Vegas algorithm as follows: This article relates to the theory of computation. ... In computing, a Las Vegas algorithm is a randomized algorithm which is correct; that is, it always produces the correct result. ...

• Suppose we have a language L recognized by both the RP algorithm A and the (possibly completely different) co-RP algorithm B.
• Given an input in L, run A on the input. If it returns YES, the answer must be YES. Otherwise, run B on the input. If it returns NO, the answer must be NO. If neither occurs, repeat this step.

Note that only one machine can ever give a wrong answer, and the chance of that machine giving the wrong answer during each repetition is 50%. This means that the chance of reaching the kth round shrinks exponentially in k, showing that the expected running time is polynomial. This shows that RP intersect co-RP is contained in ZPP. In probability theory (and especially gambling), the expected value (or mathematical expectation) of a random variable is the sum of the probability of each possible outcome of the experiment multiplied by its payoff (value). Thus, it represents the average amount one expects to win per bet if bets with identical...

To show that ZPP is contained in RP intersect co-RP, suppose we have a Las Vegas algorithm C to solve a problem. We can then construct the following RP algorithm:

• Run C for at least double its expected running time. If it gives an answer, give that answer. If it doesn't give any answer before we stop it, give NO.

By Markov's Inequality, the chance that it will yield an answer before we stop it is 1/2. This means the chance we'll give the wrong answer on a YES instance, by stopping and yielding NO, is only 1/2, fitting the definition of an RP algorithm. The co-RP algorithm is identical, except that it gives YES if C "times out". In probability theory, Markovs inequality gives an upper bound for the probability that a non-negative function of a random variable is greater than or equal to some positive constant. ...

Connection to other classes

Since ZPP=RP ∩ coRP, ZPP is obviously contained in both RP and coRP.

The class P is contained in ZPP, and some computer scientists have conjectured that P=ZPP: i.e. every Las Vegas algorithm has a deterministic polynomial-time equivalent. In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ...

It is still open whether ZPP = EXPTIME (though that is almost certainly false). The result P=ZPP would disprove this, as P ≠ EXPTIME (see time hierarchy theorem). In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... In computational complexity theory, the time hierarchy theorems are important statements that ensure the existence of certain hard problems which cannot be solved in a given amount of time. ...

External links

• ZPP - from Complexity Zoo