[#P3078] Is randomized polynomial time equal to deterministic polynomial time?

Problem. Is \(\mathrm{BPP}=\mathrm P\)? Equivalently, can every polynomial-time randomized algorithm with two-sided error at most \(1/3\) be simulated by a deterministic polynomial-time algorithm?

Randomized computation compared with deterministic simulation. — A structural automaton diagram of the statement's mathematical objects.

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

1Context

Known frontier: BPP has deterministic subexponential simulations under weaker hypotheses, and standard hardness assumptions imply BPP=P. Open boundary: Unconditional polynomial-time derandomization remains open.

2Problem setup

Definition 1 (BPP). Languages decided by a probabilistic polynomial-time algorithm whose error probability is at most 1/3 on every input.

Definition 2 (derandomization). Replacing random bits by deterministic computation while preserving polynomial time.

Remark 1. The error bound can be amplified exponentially by repetition. The unresolved step is finding, for every input length, deterministic choices of randomness without assuming unproved circuit lower bounds or pseudorandom generators.

3What counts as a solution

Give an unconditional deterministic polynomial-time simulation for every BPP machine.
Or prove a language in BPP lies outside P.

1Status

Saved packet · August 1, 2026

What counts as a solution

Saved packet status (Current status and exact unresolved remainder). OPEN as checked on 2026-08-01. Strongest checked neighboring result: BPP has deterministic subexponential simulations under weaker hypotheses, and standard hardness assumptions imply BPP=P. Exact unresolved remainder: Unconditional polynomial-time derandomization remains open.^[1][2]

1Packet records

Show recorded summaries

Record	Kind	Assessment
OPEN as checked on 2026-08-01. Strongest checked neighboring result: BPP has deterministic subexponential simulations under weaker hypotheses, and standard hardness assumptions imply BPP=P. Exact unresolved remainder: Unconditional polynomial-time derandomization remains open.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 OPEN as checked on 2026-08-01. Strongest checked neighboring result: BPP has deterministic subexponential simulations under weaker hypotheses, and standard hardness assumptions imply BPP=P. Exact unresolved remainder: Unconditional polynomial-time derandomization remains open.^[1][2] Relevance to this problem This is the dated publication status for the canonical target Is randomized polynomial time equal to deterministic polynomial time?. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details The problem was checked as open on 2026-08-01. The strongest neighboring result found in the cited sources is: BPP has deterministic subexponential simulations under weaker hypotheses, and standard hardness assumptions imply BPP=P. The exact unresolved remainder is: Unconditional polynomial-time derandomization remains open. A complete resolution must meet the following acceptance conditions: - Give an unconditional deterministic polynomial-time simulation for every BPP machine. - Or prove a language in BPP lies outside P. Open full record →
BPP has deterministic subexponential simulations under weaker hypotheses, and standard hardness assumptions imply BPP=P.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 2 BPP has deterministic subexponential simulations under weaker hypotheses, and standard hardness assumptions imply BPP=P.^[1][2] Relevance to this problem Locates the present research frontier immediately below Is randomized polynomial time equal to deterministic polynomial time?. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details BPP has deterministic subexponential simulations under weaker hypotheses, and standard hardness assumptions imply BPP=P. This leaves the following boundary unresolved: Unconditional polynomial-time derandomization remains open. The distinction is retained here so a restricted theorem, finite computation, or neighboring case is not presented as a solution of the full target. Related: Claim 1 Open full record →
The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: BPP has deterministic subexponential simulations under weaker hypotheses, and standard hardness assumptions imply BPP=P. Unresolved remainder: Unconditional polynomial-time derandomization remains open.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
attempt · Route 1 The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: BPP has deterministic subexponential simulations under weaker hypotheses, and standard hardness assumptions imply BPP=P. Unresolved remainder: Unconditional polynomial-time derandomization remains open.^[1][2] Relevance to this problem Documents why Is randomized polynomial time equal to deterministic polynomial time? was treated as a distinct open target on 2026-08-01. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 1, Reference 2 What happened The audit ran on 2026-08-01 across the cited primary literature and problem collections, Crossref, arXiv, and stable publisher records, TheoremDB published, prospecting, packet, formal, and retired corpus. It checked the exact statement, its named or normalized variants, recent status evidence, and the controlled TheoremDB corpus. Queries included: - BPP equals P open problem current derandomization - unconditional BPP P 2026 The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: BPP has deterministic subexponential simulations under weaker hypotheses, and standard hardness assumptions imply BPP=P. Unresolved remainder: Unconditional polynomial-time derandomization remains open. Related: Claim 1 Open full record →
Unconditional polynomial-time derandomization remains open.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 2 Unconditional polynomial-time derandomization remains open. Relevance to this problem For Is randomized polynomial time equal to deterministic polynomial time?, record bpp-equals-p-attempt-open-remainder (“Work at the unresolved boundary”) documents a concrete method, search boundary, or failed route. The record states: Unconditional polynomial-time derandomization remains open. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded What happened Research should address this boundary directly: Unconditional polynomial-time derandomization remains open. A claimed resolution should satisfy every item below and preserve the statement's exact quantifiers and normalizations: - Give an unconditional deterministic polynomial-time simulation for every BPP machine. - Or prove a language in BPP lies outside P. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion material

Original intake status. OPEN as checked on 2026-08-01. Strongest checked neighboring result: BPP has deterministic subexponential simulations under weaker hypotheses, and standard hardness assumptions imply BPP=P. Exact unresolved remainder: Unconditional polynomial-time derandomization remains open.

Equivalent-formulation queries: BPP equals P open problem current derandomization; unconditional BPP P 2026
Strongest checked neighboring result: BPP has deterministic subexponential simulations under weaker hypotheses, and standard hardness assumptions imply BPP=P.
Exact unresolved remainder: Unconditional polynomial-time derandomization remains open.

How the 4 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemIs randomized polynomial time equal to deterministic polynomial time?

All 3 recorded relations between these records and the problem

2See also

Multiplicative complexity of the six-bit threshold-at-least-three functiontheoretical computer science
Polynomial determinization of two-way finite automatatheoretical computer science
Logarithmic DFA separation of binary wordstheoretical computer science

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Is randomized polynomial time equal to deterministic polynomial time?.” TheoremDB. P3078. Problem statement; statement text SHA-256 df1f09ab5a79693b55469cc4c4fa4e7be8cabb0134fa76ed436d4fb131d82736. https://theoremdb.org/statement/?ref=P3078

BibTeX

@misc{theoremdb-problem-df1f09ab5a79693b55469cc4c4fa4e7be8cabb0134fa76ed436d4fb131d82736,
  title = {{Is randomized polynomial time equal to deterministic polynomial time?}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 df1f09ab5a79693b55469cc4c4fa4e7be8cabb0134fa76ed436d4fb131d82736},
  url = {https://theoremdb.org/statement/?ref=P3078}
}

Plain text: Built Markdown snapshot

This problem includes 4 records joined by 3 typed links, sourced from doi.org^[1], current as of August 1, 2026.

1Lean verification

1References

Packet source. Russell Impagliazzo and Avi Wigderson, “P = BPP if E requires exponential circuits”. Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 (1997), 220-229. DOI 10.1145/258533.258590. main theorem. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Shows strong circuit lower bounds would yield full derandomization.Also cited at R. Impagliazzo and A. Wigderson, P=BPP if E requires exponential circuits, STOC 1997. main theorem.Source used to assess the problem's recorded status.For Is randomized polynomial time equal to deterministic polynomial time?: This is the dated publication status for the canonical target Is randomized polynomial time equal to deterministic polynomial time?.Source named by the research packet.
Complexity Zoo, BPP entry. complexityzoo.net checked 2026-08-01. BPP entry. ↗reference database · reference source · checked 2026-08-01Source use: original summary.Records containments, amplification, and derandomization consequences.Source used to assess the problem's recorded status.For Is randomized polynomial time equal to deterministic polynomial time?: Records containments, amplification, and derandomization consequences.

Original TheoremDB editorial statement and source synthesis; external works are used for citation only.

[#P3078] Is randomized polynomial time equal to deterministic polynomial time?

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance