Complexity Zoo:R

From Qwiki

Jump to: navigation, search

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

R - RBQP - RE - REG - RevSPACE(f(n)) - RG - RG[1] - RHL - RHSPACE(f(n)) - RL - RNC - RP - RPkcc - RPP - RQP - RSPACE(f(n))


R: Recursive Languages

The class of decision problems solvable by a Turing machine. Often identified with the class of 'effectively computable' functions (the Church-Turing thesis).

Defined in [Tur36], [Chu41], and other seminal early papers.

Equals RE ∩ coRE.

Strictly contains PR, the primitive recursive functions (see [Kle71]).

RBQP: Strict Quantum RP

The class of problems in NP whose witnesses are in FBQP. For example, the set of square-free numbers is in coRBQP using only the fact that factoring is in FBQP. (Even without a proof that the factors are prime, the factorization proves that there is a square divisor.)

Contains RP and ZBQP, and is contained in BQP and RQP. Defined here to clarify EQP; see also ZBQP.

RE: Recursively Enumerable Languages

The class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. (If the answer is 'no,' on the other hand, the machine might never halt.)

Equivalently, the class of decision problems for which a Turing machine can list all the 'yes' instances, one by one (this is what 'enumerable' means).

A problem C is complete for RE if (1) C is in RE and (2) any problem in RE can be reduced to C by a Turing machine.

Actually there are two types of reduction: M-reductions (for many-one), in which a single instance of the original problem is mapped to an instance of C, and T-reductions (for Turing), in which an algorithm for the original problem can make arbitrarily many calls to an oracle for C.

RE-complete sets are also called creative sets for some reason.

The canonical RE-complete problem is the halting problem: i.e., given a Turing machine, does it halt when started on a blank tape?

The famous unsolvability of the halting problem [Tur36] implies that R does not equal RE.

Also, RE does not equal coRE.

RE and coRE can be generalized to the arithmetic hierarchy AH.

There are problems in RE that are neither RE-complete under T-reductions, nor in R [Fri57] [Muc56]. This is the resolution of Post's problem [Pos44].

Indeed, RE contains infinitely many nonequivalent 'T-degrees.' (A T-degree is a class of problems, all of which can be T-reduced to one another.) The structure of the T-degrees has been studied in more detail than you can possibly imagine [Sho99].

REG: Regular Languages

The class of decision problems solvable by deterministic finite automata (DFAs).

Equals the class solvable by nondeterministic finite automata (NDFAs).

Equals DSPACE(O(1)) [She59], which equals DSPACE(o(log log n)) [HLS65].

Includes, i.e., "Is the parity of the input odd?," but not "Are the majority of bits in the input 1's?" This is sometimes expressed as "finite automata can't count."

Contained in |NC1.

See e.g. [Koz97], [Gur89] for basic results on regular languages.

RevSPACE(f(n)): Reversible f(n)-Space

The class of decision problems solvable in space O(f(n)) by a reversible Turing machine (a deterministic Turing machine for which every configuration has at most one immediate predecessor).

Was shown to equal DSPACE(f(n)) [LMT97].

RG: Refereed Games

The class of problems solvable by a probabilistic polynomial-time verifier who can exchange a polynomial number of messages with two competing, computationally-unbounded provers -- one trying to convince the verifier that the answer is "yes," the other that the answer is "no." Note that the verifier can hide information from the provers. Public-coin RG amounts to SAPTIME, which equals PSPACE [Pap83].

RG is in EXP relative to any oracle [KM92]; they are equal, unrelativized [FK97b].

Contains RG[1], and is contained in QRG.

See also PCD, GPCD.

RG[1]: One-Round Refereed Games

Same as RG, except that now the verifier can exchange only a single round of messages with the two provers. A round consists of private messages from the verifier to the provers, followed by private responses from the provers to the verifier. Since the queries are private, they may as well be parallel; likewise the responses. This makes RG[1] a symmetric class, indeed a randomized analogue of S2P.

RG[1] is contained in PSPACE, and they are equal, unrelativized [FK97b].

Contains S2P and is contained in SQG.

RHL: Randomized Halting Logarithmic-Space

Has the same relation to L as RP does to P. The randomized machine must halt for every input and every setting of the random tape.

Contains undirected reachability (is there a path from vertex u to vertex v in an undirected graph?) [AKL+79].

Contained in RL.

RHSPACE(f(n)): One-Sided Error Halting Probabilistic f(n)-Space

Has the same relation to BPHSPACE(f(n)) as RP does to BPP.

RL: Randomized Logarithmic-Space

Has the same relation to L as RP does to P. The randomized machine must halt with probability 1 on any input. It must also run in polynomial time (since otherwise we would just get NL).

Contains RHL.

Contained in SC [Nis92].

[RTV05] give strong evidence that RL = L.

RNC: Randomized NC

Has the same relation to NC as RP does to P.

Contains the maximum matching problem for bipartite graphs [MVV87].

Contained in QNC.

See also: coRNC.

RP: Randomized Polynomial-Time

The class of decision problems solvable by an NP machine such that

  1. If the answer is 'yes,' at least 1/2 of computation paths accept.
  2. If the answer is 'no,' all computation paths reject.

Defined in [Gil77].

Contains the problem of testing whether an integer is prime [AH87].

For other problems in RP, see the standard text on randomized algorithms, [MR95].

Has the same p-measure as ZPP. Moreover, this measure is either zero or one. If the measure is non-zero, then ZPP = BPP = EXP [IM03].

See also: coRP, ZPP, BPP.

RPkcc: Randomized Pkcc

The class of functions F which can be computed by k players with access to shared random bits in the number-on-forehead (defined as in Pkcc) model, subject to two constraints:

  1. The communication cost (the sum of the number of random bits used and bits written to the shared blackboard) is O(polylog(n)).
  2. If F(X_1, \dots, X_k) = 1, then the players decide correctly with probably at least 2/3, whereas if F(X_1, \dots, X_k) = 0, the players always decide correctly.

NPkcc is not equal to RPkcc for all k,δ such that k\le\delta\cdot\log n [DP08].

RPP: Restricted Pseudo Polynomial-Time

The class of decision problems (x,m) (where x is an input of length |x|=n and m is an integer parameter), that are solvable by a nondeterministic (i.e. NP) machine in poly(n+m) time and O(m+log n) space simultaneously.

Defined in [Mon80].

See also FPT.

RQP: One-sided Error Extension of EQP

The class of questions that can be answered by a QTM that accepts with probability 0 when the true answer is no, and accepts with probability at least 1/2 when the true answer is yes. Since one of the probabilities has to vanish, RQP has the same technical caveats as EQP.

Contains ZQP and RBQP, and is contained in BQP.

RSPACE(f(n)): Randomized f(n)-Space

Same as RL, but for O(f(n))-space instead of logarithmic-space.

Contained in NSPACE(f(n)) and BPSPACE(f(n)).

Retrieved from "http://qwiki.stanford.edu/wiki/Complexity_Zoo:R"
Personal tools