RP (complexity)

RP (complexity)
Name	RP
Type	Complexity class
Introduced	1976
Related	BPP, P, NP, ZPP, coRP, BQP

RP (complexity) is a probabilistic complexity class capturing decision problems solvable by randomized algorithms that never falsely accept and accept yes-instances with bounded probability. RP formalizes one-sided error randomness and is central to the theoretical study of randomized computation, randomized reductions, and derandomization.

Definition

RP is defined as the class of languages L for which there exists a polynomial-time randomized Turing machine M with access to coin flips such that for every input x: if x ∈ L then Pr[M accepts x] ≥ 1/2, and if x ∉ L then Pr[M accepts x] = 0. This definition uses polynomial-time bounds in the sense of Cook–Levin theorem, Karp–Lipton theorem, and polynomial-time verification as in NP. The constant 1/2 may be replaced by any fixed inverse-polynomial or constant bound via amplification techniques related to results by Richard M. Karp, Michael O. Rabin, and notions appearing in Probabilistic Method applications by Paul Erdős.

Formal Properties

RP machines are nondeterministic in a probabilistic sense and can be formalized via probabilistic Turing machines as in early work by Michael O. Rabin and later formal treatments by Richard M. Karp and Leonid Levin. RP is closed under union and intersection; these closure properties are analogous to closure results for P and NP explored by Stephen Cook and others. Error amplification reduces one-sided error exponentially using independent repetitions, a technique connected to the amplification lemma used in analyses by Leslie Valiant and Adleman–Gill type arguments. RP is contained in BPP and in ZPP under certain constructions; relationships use reductions inspired by the Sipser–Gács theorem and structural results from the work of Noam Nisan and Avi Wigderson.

Relationships to Other Complexity Classes

RP sits between deterministic and two-sided randomized classes: P ⊆ RP ⊆ BPP ⊆ PP, with RP ⊆ NP under trivial nondeterministic simulation of randomness by witness strings as in the Cook–Levin theorem framework. The complement class coRP captures one-sided errors in the opposite direction; the intersection RP ∩ coRP equals ZPP, the zero-error randomized class studied by Christopher Umans and Gil Kalai. Containment questions like RP ?= P and RP ?= NP mirror major open problems comparable to the P versus NP problem and connect to derandomization hypotheses championed by Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Oracle separations involving RP have been demonstrated using techniques from Bennett and Gill and oracle constructions similar to those in Baker–Gill–Solovay.

Algorithms and Examples

Canonical randomized algorithms in RP include primality testing prior to deterministic breakthroughs, Monte Carlo algorithms for polynomial identity testing as in work by Richard Zippel and Rabin–Miller style tests inspired by Gary L. Miller and Michael O. Rabin, and randomized primality tests used in cryptographic protocols like those in RSA (cryptosystem). Graph non-isomorphism and certain randomized matching algorithms admit RP-style procedures via randomness exposed in algorithms by Laszlo Lovasz and Mihalis Yannakakis; randomized perfect matching algorithms by Markus Mertens and techniques from Mulmuley, Vazirani, Vazirani yield RP or related randomized class membership for combinatorial problems such as detecting perfect matchings, alongside determinant computations used in algorithms by Richard P. Brent. Randomized polynomial identity testing algorithms trace to Noga Alon and Zippel, with efficient RP procedures for algebraic problems used in the theory of interactive proofs as developed by Shafi Goldwasser and Silvio Micali.

Completeness and Hardness

RP, unlike NP, lacks natural notions of NP-style completeness under polynomial-time many-one reductions because one-sided error complicates deterministic reduction preservation; nonetheless, randomized reductions map certain search and promise problems into RP-complete settings under randomized reductions studied by Alexander Razborov and László Babai. Hardness results for RP are often conditional: derandomization results imply RP = P under hardness assumptions like those posited by Impagliazzo–Wigderson, and hardness vs randomness tradeoffs use pseudorandom generator constructions by Nisan–Wigderson to show that strong circuit lower bounds for classes such as EXP would collapse RP into P. Oracle separations by Bennett and Gill and complexity-theoretic frameworks by Fortnow provide relative hardness landscapes for RP.

Applications and Practical Implications

RP algorithms appear in practical randomized algorithms for cryptographic primality testing (RSA (cryptosystem), Diffie–Hellman key exchange contexts), randomized verification in distributed computing as studied in Leslie Lamport-style consensus contexts, and randomized subroutines in computational algebra implemented in systems influenced by work of Donald Knuth and Richard Brent. The theoretical study of RP informs derandomization efforts used in compiler optimizations and algorithm engineering influenced by results from Impagliazzo and Wigderson; in cryptography, RP-style guarantees underpin probabilistic primality tests integrated into standards and libraries associated with NIST and implementations by OpenSSL. Advances in derandomization and pseudorandom generator design by Micali, Goldreich, and Håstad affect whether RP-based heuristics can be replaced by deterministic procedures in large-scale software and hardware systems developed by Intel and IBM.

Category:Randomized complexity classes