Statements (26)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
|
| gptkbp:citation |
Sipser, Michael. Introduction to the Theory of Computation
Arora, Sanjeev; Barak, Boaz. Computational Complexity: A Modern Approach |
| gptkbp:closed |
closed under intersection
closed under union closed under complement |
| gptkbp:contains |
gptkb:PSPACE
gptkb:P_(complexity_class) PP (complexity class) |
| gptkbp:definedIn |
theoretical computer science
|
| gptkbp:describes |
decision problems solvable by probabilistic Turing machine in polynomial time with error probability less than 1/3
|
| gptkbp:errorProbabilityBound |
1/3
|
| gptkbp:errorReduction |
possible by majority vote
|
| https://www.w3.org/2000/01/rdf-schema#label |
BPP (complexity class)
|
| gptkbp:introducedIn |
1980s
|
| gptkbp:machineType |
gptkb:probabilistic_Turing_machine
|
| gptkbp:openQuestion |
Is BPP = NP?
Is BPP = P? Is P = BPP? |
| gptkbp:relatedTo |
gptkb:RP_(complexity_class)
gptkb:ZPP_(complexity_class) co-RP (complexity class) |
| gptkbp:standsFor |
Bounded-error Probabilistic Polynomial time
|
| gptkbp:bfsParent |
gptkb:NP_(complexity_class)
gptkb:P_(complexity_class) |
| gptkbp:bfsLayer |
6
|