Does randomness help? BPP versus P

Widely believed to be equal, and provably tied to circuit lower bounds nobody can prove.

Inferred from the community field; finer classification has not been reviewed.

0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

Is $\mathrm{BPP} = \mathrm{P}$ ? That is, can every language decided by a probabilistic polynomial-time algorithm with bounded two-sided error be decided deterministically in polynomial time?

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

The expectation flipped in the 1990s. Impagliazzo and Wigderson (1997) showed that if some language in $\mathrm{E}$ requires circuits of size $2^{\Omega(n)}$ , then $\mathrm{BPP} = \mathrm{P}$ . Derandomisation therefore reduces to a circuit lower bound, and hardness-versus-randomness became a two-way street: Kabanets and Impagliazzo showed derandomising polynomial identity testing implies circuit lower bounds.

Known partial results

Known: $\mathrm{P} \subseteq \mathrm{BPP} \subseteq \Sigma_2^p \cap \Pi_2^p$ (Sipser–Gács–Lautemann).
Specific derandomisations succeeded: primality testing (Agrawal–Kayal–Saxena, 2002) and undirected connectivity in logspace (Reingold, 2005).
Polynomial identity testing is the flagship remaining problem with a randomised algorithm and no deterministic one.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.