Theoretical computer science · computational complexity · pseudorandomness

P = BPP Derandomization Conjecture

Collaboration beta

Can every decision problem that admits an efficient randomized algorithm with bounded two-sided error also be solved efficiently by a deterministic algorithm?

P = BPP

Known results and sources

Two routes through the same decision landscape pose the central question: can deterministic computation always replace efficient randomized choice?

Research problem

Exact mathematical statement

\boxed{\mathbf P=\mathbf{BPP}}.

Here $\mathbf P$ is deterministic polynomial time and $\mathbf{BPP}$ is randomized polynomial time with two-sided error at most $1/3$ .

Problem infographic

Problem at a glance

A problem-first complexity-theory infographic compares deterministic polynomial-time computation with bounded-error randomized polynomial-time computation, explains the acceptance-probability gap, and presents P equals BPP as an unresolved equality rather than a proved identification. — P = BPP asks whether bounded-error randomness ever expands polynomial-time decision power; the source records exact reductions and structural barriers but explicitly reports no proof.

Current mathematical picture

Where work on P = BPP Derandomization Conjecture stands

Open conjecture

Selected route highlights from the current work. This is not yet a complete mathematical inventory.

Useful failureSource-reported limitation

For the considered local trace-certificate families, no certificate substantially below the description-entropy scale $A$ can witness that no small circuit realizes the selected constraints. Within the leading hard-language track, a deterministic E-time block procedure that repeatedly finds sufficiently low-mass ANF block words—or computes an equivalent cell vector, Walsh spectrum, or conditional path—would eliminate all small circuits and yield the required hard language.

Route status · Narrowed route

Main reductionIsolated ANF blocks

The source reports uniform isolated Theta(n)-point blocks together with ANF selectors that toggle one coefficient while preserving the others.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeSolve E-time block inference at the required precision.Task status · Ready to work on

Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

P = BPP Derandomization Conjecture in numbers

2.4kretained lines of mathematical investigation2,418 in the current working snapshot

Argument development: 1,846 · 76%
Explored or eliminated routes: 111 · 5%
Computational analysis: 153 · 6%
Open obligations: 136 · 6%
Definitions and setup: 172 · 7%

9selected mapped statements1routes investigated3open questions3contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Status checkedAug 7, 2026

Source recordedAug 7, 2026

Recommended next task

Solve E-time block inference at the required precision.

Suggested move: Freeze one exact mass model and history, then derive an N^{O(1)}-state recurrence for the full K-cell vector or Walsh spectrum, or an amortized conditional path that achieves exponential-in-B contraction and remains valid on rare fibers.

What would count as progress

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

13 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

1 recorded

Narrowed routeSource-reported limitation

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks

Solve E-time block inference at the required precision.Suggested move: Freeze one exact mass model and history, then derive an N^{O(1)}-state recurrence for the full K-cell vector or Walsh spectrum, or an amortized conditional path that achieves exponential-in-B contraction and remains valid on rare fibers.

Ready to work on

Construct a padding-invariant semantic aggregation method.Suggested move: Aggregate one unit per realizable selected trace, or a proved positive surrogate with the same minority decisions, without enumerating the 2^{Theta(A)} trace set and without reverting to identity-padding-sensitive description counts.

Ready to work on

Resolve the exact-equivalence route directly if block inference remains out of reach.Suggested move: Design and prove a deterministic polynomial-time white-box algorithm for constant-gap circuit acceptance probability, with complete runtime and uniformity analysis; by the current work’s Proposition 2.1 this would establish P = BPP directly.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 7, 2026

Current statusOpen problem

Whether every uniform bounded-error probabilistic polynomial-time decision algorithm has a deterministic polynomial-time simulation remains open. Known unconditional containments and conditional hardness-versus-randomness theorems do not establish BPP contained in P without unproved hardness assumptions.

[10][8][9]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2024
Peer reviewedChen and Tell developed uniform, non-black-box, instance-wise hardness-to-randomness results for promise-BPP under an almost-everywhere uniform hardness hypothesis; this is conditional and concerns a…[8]
2023
PreprintDoron and Tell analyzed hardness assumptions for extremely efficient high-end pseudorandom generators and proved black-box limitations, refining conditional tradeoffs rather than removing their hypotheses.[9]
2002–2004
Peer reviewedConverse-style results linked strong derandomization to circuit lower bounds. In particular, deterministic polynomial identity testing in the stated regime implies either NEXP not contained in P/poly or…[6][7]
1997
Peer reviewedImpagliazzo and Wigderson proved P = BPP assuming a language in E has Boolean circuit complexity 2^{Omega(n)}; the circuit lower bound is an unproved hypothesis.[5]

Mathematical neighborhood

Related results and reusable starting points

Current focusP = BPP

Weaker or relaxed formBPP contained in P/poly

BPP is unconditionally contained in nonuniform P/poly, but choosing a different advice string for each input length does not yield a uniform deterministic polynomial-time algorithm.

[2]

Weaker or relaxed formBPP contained in Sigma_2^P intersect Pi_2^P

BPP lies in the second level of the polynomial hierarchy, a structural upper bound strictly weaker than the desired containment in P.

[3]

Dependency or reductionHardness-versus-randomness derandomization

Hard functions yield pseudorandom generators, and an exponential Boolean-circuit lower bound for a language in E suffices for P = BPP. The hardness premise is not currently proved for general circuits.

[4][5]

Logical consequenceCircuit lower bounds from derandomization

Strong derandomization has converse lower-bound consequences. The exact implications depend on the algorithmic problem and uniformity model and do not make all derandomization statements equivalent.

[6][7]

Related problemDeterministic polynomial identity testing

Deterministic polynomial identity testing would have major circuit-lower-bound consequences, but PIT is a particular randomized algebraic problem rather than an equivalent formulation of full BPP derandomization.

[7]

Related problemConditional promise-BPP derandomization

The instance-wise theorem applies to promise-BPP under almost-everywhere uniform hardness. Promise-class scope and the conditional hypothesis prevent it from settling ordinary P = BPP.

[8]

Related problemExtreme high-end pseudorandom generators

High-end PRG constructions face model-sensitive hardness requirements and black-box limitations; these results map barriers rather than prove unconditional derandomization.

[9]

Formal and computational footholds

Existing statements, libraries, computations, and datasets that can shorten the next serious attempt.

formal library support · partial resource linkedcomplexitylib
The Lean library publicly documents concrete deterministic and probabilistic machine models and definitions of P, BPP, circuits, and P/poly. Its public description does not claim a proof of P = BPP or the full hardness-versus-randomness chain.
[11]
formal library support · partial resource linkedCSLib
The Lean Computer Science Library supplies broader developing infrastructure, but its public project materials do not establish a checked statement-aligned proof of P = BPP.
[12]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

Formalization targetA stabilized formal definition of uniform probabilistic polynomial-time Turing-machine computation, bounded two-sided error, and deterministic polynomial-time simulation.
Formalization targetChecked amplification and closure lemmas that preserve uniform polynomial bounds and distinguish languages from promise problems.
Formalization targetBoolean circuits, nonuniform advice, circuit-size lower bounds, uniform exponential time, and formal bridges between machine and circuit models.
Formalization targetPseudorandom generators, computational indistinguishability against bounded circuits, and a checked Nisan–Wigderson or Impagliazzo–Wigderson hardness-to-randomness construction with quantitative bounds.

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Research-record correctionWe corrected the cited passages. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Cited passages corrected

Research-record correctionWe clarified what the cited material supports. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Support description clarified

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

7 standing statements2 proposed statements3 open questions1 narrowed routes

Statements by mathematical role9 selected mapped statements

theorem candidate1 of 91
reduction3 of 93
lemma2 of 92
equivalence2 of 92
negative result1 of 91

Selected mathematical clusters3 mathematical clusters

Statements and reductionsClaims, implications, and derivations in the current map.17 displayed rows

retained route statementRandomized polynomial time equals deterministic polynomial time
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementGapCAPP exact equivalenceintermediate
retained route statementArbitrary-domain shatteringintermediate
retained route statementLocal certificate scale closedintermediate
retained route statementIsolated ANF blocksintermediate
retained route statementANF/value transformintermediate
retained route statementUniform E-time replayintermediate
Recorded relationshipThe source material reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
DerivationThe current work reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed

Open questionsSpecific obligations that remain open in the current routes.3 displayed rows

Research targetSolve E-time block inference at the required precision.open
Research targetConstruct a padding-invariant semantic aggregation method.open
Research targetResolve the exact-equivalence route directly if block inference remains out of reach.open

Explored routes and evidenceChallenges, computations, and approaches that have already narrowed the search.3 displayed rows · 1 route included

Useful failureSource-reported limitationreported failure
ComputationThe source records polynomial-time local block operations, zeta and Walsh transforms, fixed-r selected-trace counting, and a source report evaluator, but no implemented global E-time block-inference algorithm.Local ANF/value conversion and a K-entry output fit within E; the unresolved global aggregation over shared circuit DAGs still blocks the construction and no computation in the source proves P = BPP. · reported unreproduced
Narrowed routeSource-reported limitationFor the considered local trace-certificate families, no certificate substantially below the description-entropy scale $A$ can witness that no small circuit realizes the selected constraints. Within the leading hard-language track, a deterministic E-time block procedure that repeatedly finds sufficiently low-mass ANF block words—or computes an equivalent cell vector, Walsh spectrum, or conditional path—would eliminate all small circuits and yield the required hard language.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeSolve E-time block inference at the required precision.

1 approach has already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointSolve E-time block inference at the required precision.

P = BPP Derandomization Conjecture · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Can every decision problem that admits an efficient randomized algorithm with bounded two-sided error also be solved efficiently by a deterministic algorithm?

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references12 cited works · next context review by Nov 7, 2026

The mathematical context was checked on Aug 7, 2026. Status can be refreshed sooner after a material result or claim.

1
Computational Complexity of Probabilistic Turing Machinesoriginal source · John Gill · SIAM Journal on Computing · 1977 · DOI 10.1137/0206049 · accessed Aug 7, 2026
2
Two Theorems on Random Polynomial Timepeer reviewed result · Leonard M. Adleman · 19th Annual Symposium on Foundations of Computer Science · 1978 · DOI 10.1109/SFCS.1978.37 · accessed Aug 7, 2026
3
BPP and the polynomial hierarchypeer reviewed result · Clemens Lautemann · Information Processing Letters · 1983 · DOI 10.1016/0020-0190(83)90044-3 · accessed Aug 7, 2026
4
Hardness vs randomnesspeer reviewed result · Noam Nisan, Avi Wigderson · Journal of Computer and System Sciences · 1994 · DOI 10.1016/S0022-0000(05)80043-1 · accessed Aug 7, 2026
5
P = BPP if E requires exponential circuits: derandomizing the XOR lemmapeer reviewed result · Russell Impagliazzo, Avi Wigderson · Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing · 1997 · DOI 10.1145/258533.258590 · accessed Aug 7, 2026
6
In search of an easy witness: exponential time vs. probabilistic polynomial timepeer reviewed result · Russell Impagliazzo, Valentine Kabanets, Avi Wigderson · Journal of Computer and System Sciences · 2002 · DOI 10.1016/S0022-0000(02)00024-7 · accessed Aug 7, 2026
7
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Boundspeer reviewed result · Valentine Kabanets, Russell Impagliazzo · Computational Complexity · 2004 · DOI 10.1007/s00037-004-0182-6 · accessed Aug 7, 2026
8
Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wisepeer reviewed result · Lijie Chen, Roei Tell · SIAM Journal on Computing · 2024 · DOI 10.1137/22M1475491 · accessed Aug 7, 2026
9
On Hardness Assumptions Needed for ‘Extreme High-End’ PRGs and Fast Derandomizationpreprint · Dean Doron, Roei Tell · arXiv · 2023 · ARXIV 2311.11663 · accessed Aug 7, 2026
10
BPP: Bounded-Error Probabilistic Polynomial-Timeencyclopedia · Complexity Zoo maintainers · Complexity Zoo · accessed Aug 7, 2026
11
complexitylib: Formalization of computational complexity theory in Lean 4formalization · Samuel Schlesinger and contributors · GitHub · accessed Aug 7, 2026
12
CSLib: The Lean Computer Science Libraryformalization · CSLib contributors · GitHub · accessed Aug 7, 2026

Important qualifications

This record selects core theorem-shaping literature rather than cataloguing every restricted derandomization result.
The target is the uniform decision-class equality P = BPP; promise classes, RP, BQP, nonuniform simulation, polynomial identity testing, and cryptographic pseudorandom generators remain distinct.
All hardness-versus-randomness results retain their stated hardness hypotheses, model choices, uniformity conditions, and promise-versus-language boundaries.
The formal-resource review relies on current public project documentation and did not run external formal libraries.
Negative computation findings concern statement-aligned proof evidence, not the absence of useful experimental pseudorandomness software.
No packet source or submitted mathematical claim was read or used as authority.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces