Bounded-error randomized computation
Random choices permit a stated probability of error.
Key knowledge
BPP consists of decision languages with a probabilistic polynomial-time algorithm whose error is at most 1/3 on every input. Independent repetition and majority voting reduce a fixed error below 1/2 to any chosen positive constant.
Conditions and scope
- The probability is over the algorithm's random choices, not a distribution of inputs.
- A positive bounded-error guarantee does not become exact zero error merely by finitely many repetitions.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
BPP definition, physical page 8; independent repetition/amplification on pages 12–14; zero-error endpoint in slide lemma excluded.
2026-10-10 · BPP and bounded-error amplification; slide lemma's zero-error endpoint excluded.
Entry details
Permanent link to this entry ↗- Record identity
- info-randomized-algorithms
- Revision
- university-reference.1
- Structured reference record
- University reference