complexity class RP
E679190
Complexity class RP is a probabilistic class of decision problems solvable in polynomial time by a randomized algorithm that never falsely accepts a no-instance but may with bounded probability reject a yes-instance.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| RP | 0 |
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
complexity class
ⓘ
probabilistic complexity class ⓘ |
| abbreviationOf | Randomized Polynomial time NERFINISHED ⓘ |
| acceptanceCondition | if x is in the language then the machine accepts x with probability at least 1/2 ⓘ |
| acceptanceErrorType | false negatives allowed ⓘ |
| algorithmType | Monte Carlo algorithm with one-sided error ⓘ |
| amplificationProperty | error probability can be reduced exponentially by independent repetition ⓘ |
| canonicalExampleProblem | primality testing before deterministic polynomial-time algorithms were discovered ⓘ |
| closureProperty |
closed under intersection with deterministic polynomial-time languages
ⓘ
closed under polynomial-time many-one reductions ⓘ closed under union with deterministic polynomial-time languages ⓘ |
| complementClass | coRP ⓘ |
| complexityMeasure | time complexity measured in worst-case polynomial time ⓘ |
| computationModel | Turing machine with access to random bits ⓘ |
| decisionProblemType | languages over finite alphabets ⓘ |
| definedOver | decision problems ⓘ |
| derandomizationQuestion | whether RP equals P is a central open problem in derandomization ⓘ |
| equivalentDefinition | languages L for which there exists a probabilistic polynomial-time Turing machine M such that x in L implies Pr[M(x) accepts] ≥ 1/2 and x not in L implies Pr[M(x) accepts] = 0 ⓘ |
| errorDirection | may reject some yes-instances with bounded probability ⓘ |
| errorOn | yes-instances only ⓘ |
| errorProbabilityBound | acceptance probability for yes-instances is at least 1/2 ⓘ |
| errorType | one-sided error ⓘ |
| fullName | Randomized Polynomial time ⓘ |
| historicalContext | introduced in the study of randomized algorithms and probabilistic complexity in the late 1970s and early 1980s ⓘ |
| inputType | finite binary strings ⓘ |
| machineModel | probabilistic Turing machine ⓘ |
| noErrorGuarantee | never accepts a no-instance ⓘ |
| noErrorOn | no-instances ⓘ |
| probabilityThresholdEquivalence | changing the success probability constant does not change the class ⓘ |
| probabilityThresholdFlexibility | any constant c with 0 < c < 1 can replace 1/2 in the definition ⓘ |
| randomnessType | uses unbiased random bits ⓘ |
| rejectionCondition | if x is not in the language then the machine accepts x with probability 0 ⓘ |
| rejectionErrorType | false positives not allowed ⓘ |
| relationshipToLasVegas | Las Vegas algorithms correspond to ZPP, not RP ⓘ |
| relationToBPP |
RP is a subset of BPP
ⓘ
it is unknown whether RP equals BPP ⓘ |
| relationTocoRP | coRP is the class of complements of languages in RP ⓘ |
| relationToNP |
RP is a subset of NP ∩ coNP is not known
ⓘ
it is unknown whether RP equals NP ⓘ |
| relationToP |
P is a subset of RP
ⓘ
it is unknown whether RP equals P ⓘ |
| relationToZPP | ZPP equals RP ∩ coRP ⓘ |
| researchArea | computational complexity theory ⓘ |
| subsetOf |
BPP
NERFINISHED
ⓘ
PSPACE NERFINISHED ⓘ |
| supersetOf | P ⓘ |
| timeBound | polynomial time ⓘ |
| typicalBoundOnError | error probability can be made at most 2^{-k} for any k by repetition ⓘ |
| typicalUse | modeling efficient randomized algorithms with one-sided error ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.