RP (complexity)

Last updated

In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties:

Contents

RP algorithm (1 run)
Answer produced
Correct
answer
YesNo
Yes≥ 1/2≤ 1/2
No01
RP algorithm (n runs)
Answer produced
Correct
answer
YesNo
Yes≥ 1 − 2n≤ 2n
No01
co-RP algorithm (1 run)
Answer produced
Correct
answer
YesNo
Yes10
No≤ 1/2≥ 1/2

In other words, the algorithm is allowed to flip a truly random coin while it is running. The only case in which the algorithm can return YES is if the actual answer is YES; therefore if the algorithm terminates and produces YES, then the correct answer is definitely YES; however, the algorithm can terminate with NO regardless of the actual answer. That is, if the algorithm returns NO, it might be wrong.

Some authors call this class R, although this name is more commonly used for the class of recursive languages.

If the correct answer is YES and the algorithm is run n times with the result of each run statistically independent of the others, then it will return YES at least once with probability at least 1 − 2n. So if the algorithm is run 100 times, then the chance of it giving the wrong answer every time is lower than the chance that cosmic rays corrupted the memory of the computer running the algorithm. [1] In this sense, if a source of random numbers is available, most algorithms in RP are highly practical.

The fraction 1/2 in the definition is arbitrary. The set RP will contain exactly the same problems, even if the 1/2 is replaced by any constant nonzero probability less than 1; here constant means independent of the input to the algorithm.

Formal definition

A language L is in RP if and only if there exists a probabilistic Turing machine M, such that

Alternatively, RP can be defined using only deterministic Turing machines. A language L is in RP if and only if there exists a polynomial p and deterministic Turing machine M, such that

In this definition, the string y corresponds to the output of the random coin flips that the probabilistic Turing machine would have made. For some applications this definition is preferable since it does not mention probabilistic Turing machines.

RP in relation to other probabilistic complexity classes (ZPP, co-RP, BPP, BQP, PP), which generalise P within PSPACE. It is unknown if any of these containments are strict. Randomised Complexity Classes 2.svg
RP in relation to other probabilistic complexity classes (ZPP, co-RP, BPP, BQP, PP), which generalise P within PSPACE. It is unknown if any of these containments are strict.

The definition of RP says that a YES-answer is always right and that a NO-answer might be wrong, as a YES-instance can return a NO-answer. The complexity class co-RP is the complement, where a YES-answer might be wrong while a NO-answer is always right.

The class BPP describes algorithms that can give incorrect answers on both YES and NO instances, and thus contains both RP and co-RP. The intersection of the sets RP and co-RP is called ZPP . Just as RP may be called R, some authors use the name co-R rather than co-RP.

Connection to P and NP

Unsolved problem in computer science:

P is a subset of RP, which is a subset of NP . Similarly, P is a subset of co-RP which is a subset of co-NP . It is not known whether these inclusions are strict. However, if the commonly believed conjecture P = BPP is true, then RP, co-RP, and P collapse (are all equal). Assuming in addition that PNP, this then implies that RP is strictly contained in NP. It is not known whether RP = co-RP, or whether RP is a subset of the intersection of NP and co-NP, though this would be implied by P = BPP.

A natural example of a problem in co-RP currently not known to be in P is Polynomial Identity Testing, the problem of deciding whether a given multivariate arithmetic expression over the integers is the zero-polynomial. For instance, x·xy·y − (x + y)·(xy) is the zero-polynomial while x·x + y·y is not.

An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic Turing machines where the machine accepts if and only if at least some constant fraction of the computation paths, independent of the input size, accept. NP on the other hand, needs only one accepting path, which could constitute an exponentially small fraction of the paths. This characterization makes the fact that RP is a subset of NP obvious.

See also

Related Research Articles

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 away from 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 computer science. It asks whether every problem whose solution can be quickly verified can also be solved quickly.

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.

NP (complexity) Complexity class used to classify decision problems

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 computational complexity theory, the complexity class #P is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problems but a class of function problems. The most difficult, representative problems of this class are #P-complete.

ZPP (complexity)

In complexity theory, ZPP is the complexity class of problems for which a probabilistic Turing machine exists with these properties:

Interactive proof system

In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a prover and a verifier. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover possesses unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.

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.

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.

Complexity class Set of problems in computational complexity theory

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 Karger–Stein algorithm and Monte Carlo algorithm for minimum Feedback arc set.

In computational complexity theory, P, also known as PTIME or DTIME(nO ), 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.

PP (complexity) Class of problems in computer science

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, 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 complexity theory, the Karp–Lipton theorem states that if the Boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then

Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical complexity classes.

Generic-case complexity is a subfield of computational complexity theory that studies the complexity of computational problems on "most inputs".

References

  1. This comparison is attributed to Michael O. Rabin on p. 252 of Gasarch, William (2014), "Classifying Problems into Complexity Classes", in Memon, Atif (ed.), Advances in Computers, Vol. 95 (PDF), Academic Press, pp. 239–292.