RP (complexity)

RP (english randomized polynomial time, sometimes only with R denotes ) denotes the class of decision problems for which there is a randomized algorithm with polynomial runtime rejects any unacceptable input with probability 1 and for every thing to accept input an error probability of not more than 1 /2. The use of any other constant error bound is less than 1 does not change the definition of the class RP, by repeated application of a given RP algorithm can achieve any error bound.

This type of error is referred to as one-sided error ( one-sided error ), as opposed to the two-sided error ( two-sided error ) in the complexity class BPP.

Definition

A language is present precisely in the complexity class if a probabilistic Turing machine exists, for which:

• Runs for all the inputs in polynomial time

The constant 1/2 is arbitrarily selected. Any constant strictly greater than 0 leads to an equivalent definition.

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

Properties

RP is closed under union and intersection. This means that for two languages ​​as well. It is unknown whether RP is closed under complementation, the Komplementklasse of RP is the complexity class co -RP.

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

Relation to other complexity classes

Both RP and co -RP lie between the classes ZPP ( RP = co -RP ) and BPP, so it applies ZPP ⊆ RP ⊆ BPP and ZPP ⊆ RP ⊆ co - BPP.

In addition, RP ⊆ NP and co -RP ⊆ co - NP.

If NP ⊆ BPP, then NP = RP is even considered.