Skip to content

Problems News About Submit

← All problems

BPP versus P

$BPP$ consists of languages decided in polynomial time by randomized algorithms whose error probability is at most $1/3$ on every input.

Is $BPP = P$ ?

Abstract

Randomness yields simple and fast algorithms for many tasks, but it may not enlarge the set of problems solvable in polynomial time. The question connects pseudorandom generator construction with circuit lower bounds.

Background and progress

Randomized polynomial time was formalized to capture bounded-error efficient algorithms.
Pseudorandom generators provided a route from hardness assumptions to deterministic simulation.
Impagliazzo and Wigderson proved a central hardness-versus-randomness conditional result.

Reference papers

P = BPP if E Requires Exponential CircuitsRussell Impagliazzo, Avi WigdersonSTOC · 1997 ↗

© 2026 OpenTCS · All rights reserved.

Coming soon

Organizer

Boyuan Wang

Minghan Wang

Bochao Li

Hongwei Hu