TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-09-12

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Adleman's theorem: BPP is contained in P/poly

Statement

If $L \in B P P$ , then there exist a deterministic polynomial-time machine $D$ and advice strings $a_{n}$ of polynomial length such that $D (x, a_{∣ x ∣})$ decides $L$ . Equivalently, $L \in P / p o l y$ .

Facts & Assumptions

Given: a language $L \in B P P$ .

[L1]

BPP error can be reduced to exponentially small error while staying in probabilistic polynomial time (BPP amplification to exponentially small error).

[L2]

The finite union bound says that the probability of a finite union is at most the sum of the individual probabilities (The finite union bound).

Proof

technique · direct

1.1

By [L1], for each input length $n$ there is a probabilistic polynomial-time machine $M_{n}$ deciding $L$ on length- $n$ inputs with error at most $2^{- (n + 2)}$ . Let $m (n)$ be the number of random bits used by $M_{n}$ ; this is polynomial in $n$ .

L1given

2.1

For each word $x \in {0, 1}^{n}$ , let $B_{x}$ be the event that the random string $r \in {0, 1}^{m (n)}$ makes $M_{n}$ err on $x$ . Then $P (B_{x}) \leq 2^{- (n + 2)}$ . By [L2], $P (⋃_{x \in {0, 1}^{n}} B_{x}) \leq 2^{n} \cdot 2^{- (n + 2)} = 1 / 4 < 1$ . So there exists some random string $r_{n}$ for which no event $B_{x}$ occurs: that one string makes $M_{n}$ correct on every length- $n$ input simultaneously.

L2step 1.1algebra

3.1

Use $a_{n} : = r_{n}$ as advice. The deterministic advice machine $D$ for input $x$ of length $n$ simulates $M_{n}$ on $(x, a_{n})$ with the randomness tape fixed to $a_{n}$ . By step 2.1 this simulation is correct on every length- $n$ input, and the advice length is $m (n) = p o l y (n)$ . Therefore $L$ has polynomial advice and hence lies in $P / p o l y$ .

step 2.1construct∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

7 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach (standard reference, not scraped)
Eric Blais, Models of Computation, 15. P vs. BPP (standard reference, not scraped)