Complexity Zoo:R

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] - R_HL - R_HSPACE(f(n)) - RL - RNC - RNC¹ - RP - RP^cc - RP_$k$^cc - 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 NC¹.

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].

See also PCD, GPCD.

---

RG(k): k-turn Refereed Games

Same as RG, except that now the verifier exchanges exactly k messages with each prover where k is a polynomial-bounded function of the input length. Messages are exchanged in parallel. By definition, RG(poly) = RG. See also RG(1) and RG(2).

Other than trivial bounds, very little is known of RG(k) for intermediate values of k. For example, does RG(k) = PSPACE for each constant $k\geq 2$?

---

RG(2): Two-turn (one-round) Refereed Games

Same as RG, except that now the verifier can exchange only two messages with each prover. Messages are exchanged in parallel, so the verifier cannot process the answer from one prover before preparing the question for the other. See also RG(k).

RG(2) is contained in PSPACE, and they are equal, unrelativized [FK97b].

---

RG(1): One-turn Refereed Games

The class of problems for which there exists a BPP machine M such that, on input x:

1. If the answer is 'yes,' then there exists a distribution Y such that for all distributions Z, M(x,Y,Z) accepts with probability at least 2/3.
2. If the answer is 'no,' then there exists a distribution Z such that for all distributions Y, M(x,Y,Z) rejects with probability at least 2/3.

In other words, it's the same as RG(k) for $k=1$, the class of problems that admit interactive proofs with competing provers in which there's no communication from the verifier back to the provers.

RG(1) trivially contains S₂P. Indeed, RG(1) can be viewed as a randomized version of S₂P.

RG(1) is trivially contained in RG(2) (and hence PSPACE).

---

R_HL: 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.

---

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

Has the same relation to BP_HSPACE(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 R_HL.

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] (implicitly: the class VPP that is defined is equivalent to RP by running the recognizer as many times as necessary to reach probability 1/2).

Contains the problem of testing whether an integer is prime [AH87], although this problem was subsequently shown to be in P [AKS02].

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.

---

RP^cc: Communication Complexity RP

The analogue of P^cc for bounded one-sided error probabilistic communication complexity.

Contains the complement of the EQUALITY function.

---

RP_$k$^cc: Randomized P_$k$^cc

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 P_$k$^cc) 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({\textrm {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.

NP_$k$^cc is not equal to RP_$k$^cc for $k\leq (1-\delta )\cdot \log n$ players, for any constant $\delta >0$ [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. (Just as an RL machine must run in polynomial time, so an RSPACE(f(n)) machine must run in 2^O(f(n)) time.)

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