RP (complexity class)

RP in relation to other probabilistic complexity classes

RP ( English randomized polynomial time , sometimes just called R ) denotes the class of decision problems for which there is a randomized algorithm with polynomial running time that rejects every unacceptable input with a probability of 1 and for every input that is accepted an error probability of has at most 1/2. The use of any other constant error bound less than 1 does not change the definition of the class RP; by using a given RP algorithm several times, any desired error bound can be achieved.

This type of error is known as a one-sided error, in contrast to the two-sided error in the complexity class BPP .

definition

A language is in the complexity class if and only if there is a probabilistic Turing machine for which the following applies: ${\ displaystyle {\ mathcal {L}}}$ ${\ displaystyle {\ mathcal {RP}}}$ ${\ displaystyle M}$

${\ displaystyle M}$ runs for all inputs in polynomial time
${\ displaystyle x \ in {\ mathcal {L}} \ Rightarrow Pr [M (x) = 1] \ geq {\ frac {1} {2}}}$
${\ displaystyle x \ notin {\ mathcal {L}} \ Rightarrow Pr [M (x) = 0] = 1}$

The constant 1/2 is chosen arbitrarily. Any constant real greater than 0 and less than 1 leads to an equivalent definition.

In contrast to the complexity class ZPP , it is required here that the runtime of the Turing machine is polynomial for all inputs. This requirement can be weakened so that, as with ZPP, the only requirement is that the expected value of the running time is limited by a polynomial; the two definitions are equivalent. ${\ displaystyle M}$

properties

RP is completed under union and editing. That means that for two languages too . It is unknown whether RP is completed with formation of complement, the complement class of RP is the complexity class co-RP . ${\ displaystyle L_ {1}, L_ {2} \ in {\ mathcal {RP}}}$ ${\ displaystyle L_ {1} \ cup L_ {2}, L_ {1} \ cap L_ {2} \ in {\ mathcal {RP}}}$

There is no known RP-complete problem and there are indications that there are no RP-complete problems.

Relationship to other complexity classes

Both RP and co-RP lie between the classes ZPP (= RP co-RP) and BPP , so ZPP ⊆ RP ⊆ BPP and ZPP ⊆ co-RP ⊆ BPP apply. ${\ displaystyle \ cap}$

Furthermore we have RP ⊆ NP and co-RP ⊆ co-NP .

If NP ⊆ BPP, then even NP = RP.

Individual evidence

^ ^A ^b Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach . Cambridge University Press, 2009, ISBN 978-0-521-42426-4 , pp. 133 .
^ ^A ^b ^c Daniel Pierre Bovet and Pierluigi Crescenzi: Introduction to the Theory of Complexity . Prentice Hall, 1994, ISBN 0-13-915380-2 , pp. 195 .
^ Daniel Pierre Bovet and Pierluigi Crescenzi: Introduction to the Theory of Complexity . Prentice Hall, 1994, ISBN 0-13-915380-2 , pp. 198.202 .
↑ Johannes Köbler, Uwe Schöning, Jacobo Torán: The Graph Isomorphism Problem - It's Structural Complexity . Birkhäuser, 1993, ISBN 3-7643-3680-3 , p. 73 .

literature

Ingo Wegener: Complexity Theory (pp. 31–34) ISBN 3540001611

Köbler, Schöning, Toran: The Graph Isomorphism Problem - It's Structural Complexity (p. 68 ff.) - ISBN 3-7643-3680-3

Web links

RP . In: Complexity Zoo. (English)

[AB133-1] A ^b Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach . Cambridge University Press, 2009, ISBN 978-0-521-42426-4 , pp. 133 .

[BoCr195-2] A ^b ^c Daniel Pierre Bovet and Pierluigi Crescenzi: Introduction to the Theory of Complexity . Prentice Hall, 1994, ISBN 0-13-915380-2 , pp. 195 .

[BoCr198-3] Daniel Pierre Bovet and Pierluigi Crescenzi: Introduction to the Theory of Complexity . Prentice Hall, 1994, ISBN 0-13-915380-2 , pp. 198.202 .

[KST73-4] Johannes Köbler, Uwe Schöning, Jacobo Torán: The Graph Isomorphism Problem - It's Structural Complexity . Birkhäuser, 1993, ISBN 3-7643-3680-3 , p. 73 .