complexity class BPP
E679189
Complexity class BPP is the set of decision problems that can be efficiently solved by a probabilistic Turing machine with a bounded probability of error.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| BPP | 0 |
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf | complexity class ⓘ |
| abbreviationFor | Bounded-Error Probabilistic Polynomial Time NERFINISHED ⓘ |
| characterizedBy | probabilistic Turing machine ⓘ |
| closureProperty |
closed under complement
ⓘ
closed under intersection ⓘ closed under polynomial-time many-one reductions ⓘ closed under union ⓘ |
| comparisonClass | NP ⓘ |
| complexityMeasure | randomized time complexity ⓘ |
| conjecturedEqualTo | P ⓘ |
| contains |
P
ⓘ
RP ∩ coRP ⓘ ZPP NERFINISHED ⓘ |
| decisionProblemType | language recognition ⓘ |
| definedBy | existence of probabilistic polynomial-time algorithm with bounded error ⓘ |
| definedOver | decision problems ⓘ |
| derandomizationImplication |
BPP = P if sufficiently strong pseudorandom generators exist
ⓘ
BPP = P under certain circuit lower bound assumptions ⓘ |
| derandomizationQuestion | whether BPP = P ⓘ |
| errorAmplificationMethod | majority vote over independent runs ⓘ |
| errorBound | bounded away from 1/2 ⓘ |
| errorDirection | allows both false positives and false negatives ⓘ |
| errorReductionProperty | error can be reduced exponentially by repetition ⓘ |
| errorType | two-sided error ⓘ |
| fullName | Bounded-Error Probabilistic Polynomial Time NERFINISHED ⓘ |
| hasCompleteProblems | unknown under standard reductions ⓘ |
| historicalContext | studied since 1980s in randomized algorithms literature ⓘ |
| inputType | finite binary strings ⓘ |
| introducedInField | computational complexity theory ⓘ |
| machineModel | probabilistic polynomial-time Turing machine ⓘ |
| oracleModel | BPP^BPP = BPP ⓘ |
| probabilitySpace | uniform distribution over random bits ⓘ |
| relatedTo |
RP
ⓘ
ZPP NERFINISHED ⓘ coRP ⓘ |
| relationshipToNP | unknown whether NP ⊆ BPP ⓘ |
| relationshipToPH | if BPP = P then PH collapses no further than in deterministic case ⓘ |
| robustnessProperty | choice of constant error bound in (0,1/2) does not change the class ⓘ |
| subsetOf |
PP
ⓘ
PSPACE NERFINISHED ⓘ SUBEXP (under standard definitions) ⓘ |
| supersetOf | P ⓘ |
| timeBound | polynomial time ⓘ |
| typicalAcceptanceCondition | yes-instances accepted with probability at least 2/3 ⓘ |
| typicalErrorBound |
at most 1/3
ⓘ
at most 1/4 ⓘ |
| typicalRejectionCondition | no-instances accepted with probability at most 1/3 ⓘ |
| typicalResource | polynomial number of random bits ⓘ |
| uses | random bits ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.