ZPP in relation to other probabilistic complexity classes (RP, co-RP, BPP, BQP, PP), which generalise P within PSPACE. It is unknown if any of these containments are strict.
The running time is polynomial in expectation for every input.
In other words, if the algorithm is allowed to flip a truly-random coin while it is running, it will always return the correct answer and, 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. Such an algorithm is called a Las Vegas algorithm.
Alternatively, ZPP can be defined as the class of problems for which a probabilistic Turing machine exists with these properties:
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.
It returns DO NOT KNOW with probability at most 1/2 for every input (and the correct answer otherwise).
The two definitions are equivalent.
The definition of ZPP is based on probabilistic Turing machines, but, for clarity, note that other complexity classes based on them include BPP and RP. The class BQP is based on another machine with randomness: the quantum computer.
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 bothRP and co-RP has a Las Vegas algorithm as follows:
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, run A on the input for one step. If it returns YES, the answer must be YES. Otherwise, run B on the input for one step. 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 at most 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.
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 at least 1/2. This means the chance we'll give the wrong answer on a YES instance, by stopping and yielding NO, is at most 1/2, fitting the definition of an RP algorithm. The co-RP algorithm is identical, except that it gives YES if C "times out".
Witness and proof
The classes NP, RP and ZPP can be thought of in terms of proof of membership in a set.
Definition: A verifier V for a set X is a Turing machine such that:
if x is in X then there exists a string w such that V(x,w) accepts;
if x is not in X, then for all strings w, V(x,w) rejects.
The string w can be thought of as the proof of membership. In the case of short proofs (of length bounded by a polynomial in the size of the input) which can be efficiently verified (V is a polynomial-time deterministic Turing machine), the string w is called a witness.
Notes:
The definition is very asymmetric. The proof of x being in X is a single string. The proof of x not being in X is the collection of all strings, none of which is a proof of membership.
For all x in X there must be a witness to its membership in X.
The witness need not be a traditionally construed proof. If V is a probabilistic Turing machine which could possibly accept x if x is in X, then the proof is the string of coin flips which leads the machine to accept x (provided all members in X have some witness and the machine never accepts a non-member).
The co-concept is a proof of non-membership, or membership in the complement set.
The classes NP, RP and ZPP are sets which have witnesses for membership. The class NP requires only that witnesses exist. They may be very rare. Of the 2f(|x|) possible strings, with f a polynomial, only one need cause the verifier to accept (if x is in X. If x is not in X, no string will cause the verifier to accept).
For the classes RP and ZPP any string chosen at random will likely be a witness.
The corresponding co-classes have witness for non-membership. In particular, co-RP is the class of sets for which, if x is not in X, any randomly chosen string is likely to be a witness for non-membership. ZPP is the class of sets for which any random string is likely to be a witness of x in X, or x not in X, which ever the case may be.
Connecting this definition with other definitions of RP, co-RP and ZPP is easy. The probabilistic polynomial-time Turing Machine V*w(x) corresponds to the deterministic polynomial-time Turing Machine V(x, w) by replacing the random tape of V* with a second input tape for V on which is written the sequence of coin flips. By selecting the witness as a random string, the verifier is a probabilistic polynomial-time Turing Machine whose probability of accepting x when x is in X is large (greater than 1/2, say), but zero if x ∉ X (for RP); of rejecting x when x is not in X is large but zero if x ∈ X (for co-RP); and of correctly accepting or rejecting x as a member of X is large, but zero of incorrectly accepting or rejecting x (for ZPP).
By repeated random selection of a possible witness, the large probability that a random string is a witness gives an expected polynomial time algorithm for accepting or rejecting an input. Conversely, if the Turing Machine is expected polynomial-time (for any given x), then a considerable fraction of the runs must be polynomial-time bounded, and the coin sequence used in such a run will be a witness.
ZPP should be contrasted with BPP. The class BPP does not require witnesses, although witnesses are sufficient (hence BPP contains RP, co-RP and ZPP). A BPP language has V(x,w) accept on a (clear) majority of strings w if x is in X, and conversely reject on a (clear) majority of strings w if x is not in X. No single string w need be definitive, and therefore they cannot in general be considered proofs or witnesses.
Complexity-theoretic properties
It is known that ZPP is closed under complement; that is, ZPP = co-ZPP.
ZPP is low for itself, meaning that a ZPP machine with the power to solve ZPP problems instantly (a ZPP oracle machine) is not any more powerful than the machine without this extra power. In symbols, ZPPZPP = ZPP.
ZPPNPBPP = ZPPNP.
NPBPP is contained in ZPPNP.
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.
There exists an oracle relative to which ZPP = EXPTIME. A proof for ZPP = EXPTIME would imply that P ≠ ZPP, as P ≠ EXPTIME (see time hierarchy theorem).
In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.
In computational complexity theory, NP is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a single operation. The problem can be of any complexity class. Even undecidable problems, such as the halting problem, can be used.
In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties:
In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turing machine can—unlike a deterministic Turing Machine—have stochastic results; that is, on a given input and instruction state machine, it may have different run times, or it may not halt at all; furthermore, it may accept an input in one execution and reject the same input in another execution.
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output are random variables.
In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.
In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability. A standard proof, as used in the verifier-based definition of the complexity class NP, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs. However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way.
In computing, a Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain probability. Two examples of such algorithms are the Karger–Stein algorithm and the Monte Carlo algorithm for minimum feedback arc set.
In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977.
In computational complexity theory, an Arthur–Merlin protocol, introduced by Babai (1985), is an interactive proof system in which the verifier's coin tosses are constrained to be public. Goldwasser & Sipser (1986) proved that all (formal) languages with interactive proofs of arbitrary length with private coins also have interactive proofs with public coins.
In computational complexity theory, the complexity class NEXPTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time .
In computational complexity theory, NL is the complexity class containing decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.
Randomized Logarithmic-space (RL), sometimes called RLP, is the complexity class of computational complexity theory problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with one-sided error. It is named in analogy with RP, which is similar but has no logarithmic space restriction.
In computational complexity theory, P/poly is a complexity class representing problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial-size circuit families. It can also be defined equivalently in terms of Turing machines with advice, extra information supplied to the Turing machine along with its input, that may depend on the input length but not on the input itself. In this formulation, P/poly is the class of decision problems that can be solved by a polynomial-time Turing machine with advice strings of length polynomial in the input size. These two different definitions make P/poly central to circuit complexity and non-uniform complexity.
In computational complexity theory, a certificate is a string that certifies the answer to a computation, or certifies the membership of some string in a language. A certificate is often thought of as a solution path within a verification process, which is used to check whether a problem gives the answer "Yes" or "No".
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
