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.
All labels observed (1)
| Label | Occurrences |
|---|---|
| complexity class BPP canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T7666903 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: complexity class BPP Context triple: [Complexity Theory, defines, complexity class BPP]
-
A.
NP-completeness
NP-completeness is a central concept in computational complexity theory that classifies decision problems believed to be among the hardest in NP, such that a polynomial-time solution to any one of them would yield polynomial-time solutions to all problems in NP.
-
B.
Valiant–Vazirani theorem
The Valiant–Vazirani theorem is a fundamental result in computational complexity theory showing that solving unique solutions of NP problems is, under randomized reductions, as hard as solving general NP problems, with major implications for the study of randomness and hardness of approximation.
-
C.
PCP theorem
The PCP theorem is a fundamental result in computational complexity theory stating that every problem in NP has probabilistically checkable proofs that can be verified by examining only a constant number of bits, with major implications for the hardness of approximation.
-
D.
Randomness and Computation
"Randomness and Computation" is Shafi Goldwasser's influential doctoral thesis that helped lay the foundations of modern complexity theory and cryptography by rigorously exploring the role of randomness in efficient computation.
-
E.
P versus NP problem
The P versus NP problem is a central unsolved question in theoretical computer science that asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: complexity class BPP Target entity description: 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.
-
A.
NP-completeness
NP-completeness is a central concept in computational complexity theory that classifies decision problems believed to be among the hardest in NP, such that a polynomial-time solution to any one of them would yield polynomial-time solutions to all problems in NP.
-
B.
Valiant–Vazirani theorem
The Valiant–Vazirani theorem is a fundamental result in computational complexity theory showing that solving unique solutions of NP problems is, under randomized reductions, as hard as solving general NP problems, with major implications for the study of randomness and hardness of approximation.
-
C.
PCP theorem
The PCP theorem is a fundamental result in computational complexity theory stating that every problem in NP has probabilistically checkable proofs that can be verified by examining only a constant number of bits, with major implications for the hardness of approximation.
-
D.
Randomness and Computation
"Randomness and Computation" is Shafi Goldwasser's influential doctoral thesis that helped lay the foundations of modern complexity theory and cryptography by rigorously exploring the role of randomness in efficient computation.
-
E.
P versus NP problem
The P versus NP problem is a central unsolved question in theoretical computer science that asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.
- F. None of above. chosen
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf | complexity class ⓘ |
| abbreviationFor | Bounded-Error Probabilistic Polynomial Time ⓘ |
| 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 ⓘ |
| 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 ⓘ |
| 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 ⓘ 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 ⓘ 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 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: complexity class BPP Description of subject: 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.
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.