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).
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.)
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?
Also, RE does not equal coRE.
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).
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.
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).
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(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 ?
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(1): One-turn Refereed Games
The class of problems for which there exists a BPP machine M such that, on input x:
- 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.
- 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 , the class of problems that admit interactive proofs with competing provers in which there's no communication from the verifier back to the provers.
RHL: Randomized Halting Logarithmic-Space
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
RL: Randomized Logarithmic-Space
RNC: Randomized NC
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
- If the answer is 'yes,' at least 1/2 of computation paths accept.
- 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).
For other problems in RP, see the standard text on randomized algorithms, [MR95].
RPcc: Communication Complexity RP
The analogue of Pcc for bounded one-sided error probabilistic communication complexity.
RPcc: Randomized Pcc
The class of functions which can be computed by players with access to shared random bits in the number-on-forehead (defined as in Pcc) model, subject to two constraints:
- The communication cost (the sum of the number of random bits used and bits written to the shared blackboard) is .
- If , then the players decide correctly with probably at least 2/3, whereas if , the players always decide correctly.
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.
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 2O(f(n)) time.)