# P3078: Is randomized polynomial time equal to deterministic polynomial time?

- ID: `P3078`
- Reference: `bpp-equals-p`
- Page: https://theoremdb.org/statements/P3078
- Record maturity: Reviewed problem with recorded work

## 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?

### Context

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.

### Problem setup

- **Definition (BPP).** Languages decided by a probabilistic polynomial-time algorithm whose error probability is at most 1/3 on every input.
- **Definition (derandomization).** Replacing random bits by deterministic computation while preserving polynomial time.
- **Remark.** 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.

### What counts as a solution

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

## 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. [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (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.

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.

### Background and intake notes

- 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.
- The release review checked 2 structured sources on 2026-08-01.
- 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.

### Other known results

- **Claim 2** (supported): BPP has deterministic subexponential simulations under weaker hypotheses, and standard hardness assumptions imply BPP=P. [1](#reference-1) [2](#reference-2)

### Prior approaches

- **Route 1** (supported): 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](#reference-1) [2](#reference-2)

### Open directions

- **Route 2** (reported): Unconditional polynomial-time derandomization remains open.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `bpp-equals-p`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://doi.org/10.1145/258533.258590
   - Also cited at R. Impagliazzo and A. Wigderson, P=BPP if E requires exponential circuits, STOC 1997. main theorem
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - Shows strong circuit lower bounds would yield full derandomization.
   - 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.
2. <a id="reference-2"></a>Complexity Zoo, BPP entry. complexityzoo.net checked 2026-08-01. BPP entry https://complexityzoo.net/Complexity_Zoo:B#bpp
   - reference_database; reference source; checked 2026-08-01
   - Source 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.