Papex

Open problem · Computer science · Open

P versus BPP

Can every problem that a randomised algorithm solves efficiently also be solved efficiently without randomness?

Summary

BPP holds the problems solvable in polynomial time by algorithms that use random choices and may err with small probability. P = BPP is widely conjectured; primality testing was derandomised in 2002, but polynomial identity testing is still not known to be in P.

Why it is open

P is the class of problems that a deterministic algorithm solves in polynomial time, and BPP (bounded-error probabilistic polynomial time) contains the problems for which a polynomial-time algorithm that flips coins gives the right answer with probability at least 2/3 on every input; repeating it and taking the majority answer makes errors as rare as needed [5]. Every problem in P is in BPP [4, 5], and the conjecture P = BPP says that randomness can always be removed with at most a polynomial slowdown [1, 5]. John Gill, who formally defined BPP in 1977, already conjectured it [4].

Without assumptions, trying every possible random string shows only that BPP is contained in exponential time, and in 2012 Salil Vadhan wrote that this "remains the best unconditional upper-bound" on the deterministic time needed for BPP; it was even "consistent with current knowledge that BPP equals NEXP", nondeterministic exponential time [4]. BPP is known to lie in the second level of the polynomial hierarchy, so P = NP would imply P = BPP [4, 5]. A proof that P ≠ BPP would therefore also prove P ≠ NP [4] (see the Papex page P versus NP).

A proof of P = BPP meets its own obstacles: derandomising a single problem in BPP, polynomial identity testing, would already imply circuit lower bounds that no one can yet prove [3, 4]. In 2008 Scott Aaronson and Avi Wigderson showed that any proof of P = BPP needs "non-algebrizing" techniques, so that the arithmetic methods behind results such as IP = PSPACE cannot suffice on their own [5].

No prize is attached, and this page's status follows the Wikipedia list of unsolved problems in computer science, which includes the "P = BPP problem" and, separately, asks whether polynomial identity testing can be derandomised [12].

What is known

Randomised algorithms (1970s). Vadhan dates the algorithmic power of randomness to the 1970s, with examples such as Berlekamp's algorithm for factoring polynomials over large finite fields and randomised primality tests [4]. Polynomial identity testing (PIT) asks whether a polynomial, given as an arithmetic formula or circuit, is identically zero [4, 5]. The randomised algorithm, found independently by DeMillo and Lipton, by Schwartz and by Zippel, evaluates it at a random point: by the Schwartz–Zippel lemma, a nonzero polynomial of degree d vanishes at a point chosen at random from a set S with probability at most d/|S| [4].

Primality (1974–2004). Miller's deterministic primality test needed the extended Riemann hypothesis; Rabin turned it into an unconditional randomised test, and Solovay and Strassen gave another [2]. In 2002 Manindra Agrawal, Neeraj Kayal and Nitin Saxena gave an unconditional deterministic polynomial-time test [5], published in 2004 with a running time of Õ(log^(15/2) n) [2]. Their test starts from the identity (X + a)^n = X^n + a (mod n), which, for a coprime to n, holds exactly when n is prime and was the basis of an earlier randomised test [2]; Aaronson describes it as "a derandomization of one extremely special case of PIT" [5].

Hardness versus randomness (1980s–2001). A pseudorandom generator stretches a short random seed into a long string that a given class of algorithms cannot tell from random [4]; one that fools polynomial-time algorithms with a seed of O(log n) bits would give P = BPP, because a deterministic algorithm can try every seed [4]. Building on Blum and Micali, Yao constructed generators from one-way permutations and obtained subexponential-time simulations of randomised algorithms; Nisan and Wigderson later needed only a hard function in exponential time [1]. In 1997 Russell Impagliazzo and Wigderson proved that if some problem in E, deterministic time 2^O(n), requires circuits of size 2^Ω(n), then P = BPP [1]. Vadhan calls this hypothesis "quite plausible", since SAT lies in E and is "commonly believed" to need circuits of that size [4]. In a uniform version, published in 2001, Impagliazzo and Wigderson showed that if EXP ≠ BPP, then BPP has subexponential-time deterministic simulations that work on average, for infinitely many input lengths [4].

Derandomisation implies lower bounds (2002–2004). Impagliazzo, Valentine Kabanets and Wigderson showed in 2002 that if promise-BPP = promise-P, which implies P = BPP, then NEXP has no polynomial-size circuits [4]. Kabanets and Impagliazzo showed that a deterministic polynomial-time PIT algorithm would imply that NEXP has no polynomial-size circuits or that the permanent has no polynomial-size arithmetic circuits: "establishing that RP=coRP or BPP=P would require proving superpolynomial lower bounds for Boolean or arithmetic circuits" [3]. Aaronson notes that it is unclear whether to read this as a path to lower bounds or as an explanation of why derandomising PIT will be hard [5].

Recent results (2020–2025). In 2020 Dean Doron, Dana Moshkovitz, Justin Oh and David Zuckerman showed that, assuming exponential lower bounds against nondeterministic circuits, a randomised algorithm running in time t can be made deterministic in time t^(2+α) for any α > 0; this is nearly optimal, since under complexity-theoretic assumptions some problems need a quadratic slowdown [6]. In 2021 Lijie Chen and Roei Tell derived promise-BPP = promise-P from a uniform assumption, that some efficiently computable function is hard for probabilistic algorithms on almost all inputs, and showed that a version of this assumption is also necessary [7]. Also in 2021 Nutan Limaye, Srikanth Srinivasan and Sébastien Tavenas proved the first superpolynomial lower bounds against constant-depth algebraic circuits over fields of characteristic 0, which give the first deterministic subexponential-time PIT algorithm for all small-depth circuits [8].

What researchers believe. "Today, most complexity theorists conjecture" that P = BPP, Aaronson wrote in 2016 [5]. In 1997 Impagliazzo and Wigderson wrote that "the evidence favors using as a working hypothesis that P = BPP" [1].

Recent claims. On 6 October 2026 OpenAI released openai/math, manuscripts "produced by an internal OpenAI model" and "at different stages of verification" [9]. One, dated 23 September 2026, claims L = RL = BPL: randomised algorithms that run in polynomial time with logarithmic memory can be made deterministic with logarithmic memory [9]. A Lean formalisation of that equality was added on 8 October; the review status recorded for the repository's formalisation catalogue is "unchecked" [9]. Another, dated 4 October 2026 and without a formalisation, claims a deterministic polynomial-time algorithm that factors polynomials over prime fields [9]. Aaronson called L = BPL "one of the great derandomization conjectures short of P=BPP", whose "truth was never in serious doubt", and noted that P = BPP is not among the claims, "surely not for lack of trying" [10]. On 7 October Lance Fortnow wrote that "these proofs haven't been fully verified" [11]. In 2012 Vadhan listed RL = L and BPL = L as open problems [4]; on 15 October 2026 the Wikipedia list still included both the L = RL problem and the P = BPP problem [12].

Main approaches

Circuit lower bounds. Prove that some problem in E needs large circuits and apply the hardness-versus-randomness construction [1]. Strongest evidence: the implication itself [1], now with nearly optimal slowdown under a stronger assumption [6]. Main difficulty: the required lower bounds are far beyond current techniques; Aaronson observes that if we knew how to prove one, "perhaps we could prove P ≠ NP as well" [5], and Kabanets and Impagliazzo show that some circuit lower bound cannot be avoided [3].

Uniform and instance-wise hardness. Assume hardness against probabilistic algorithms rather than circuits, and allow derandomisation algorithms that are not black-box [7]. Strongest evidence: Chen and Tell's result, which suggests "a potential equivalence" between derandomisation and such hardness [7]. Main difficulty: hardness on almost all inputs is stronger than the usual requirement of failing on one input of each length, and it is unproven [7].

One problem at a time. Remove randomness from particular algorithms, as for primality [2] and for PIT on restricted circuits [8]. Strongest evidence: primality in P [2] and subexponential-time PIT for constant-depth circuits [8]. Main difficulty: a polynomial-time algorithm for general PIT would itself imply circuit lower bounds [3], and the constant-depth algorithm runs in subexponential, not polynomial, time [8].

Cryptographic generators. Build generators from one-way functions [4]. Strongest evidence: if one-way functions exist, BPP lies in subexponential time [4]. Main difficulty: such generators cannot have a seed of O(log m) bits for output length m, so they stop short of P = BPP [4], and whether one-way functions exist is itself open (see Existence of one-way functions).

Open sub-questions

  1. Nearly optimal slowdown. Can the t^(2+α) derandomisation of Doron and colleagues be obtained from lower bounds against deterministic, rather than nondeterministic, circuits [6]?
  2. Beyond constant depth. Can deterministic PIT for constant-depth algebraic circuits be brought from subexponential to quasi-polynomial time, or extended to depth that grows with the input [8]?
  3. Almost all inputs. Does a standard worst-case uniform lower bound imply the hardness on almost all inputs that Chen and Tell use [7]?
  4. Lower bounds for E. Does promise-BPP = promise-P imply that E has no polynomial-size circuits, Vadhan's open problem 8.8 [4]?
  5. Seed length from one-way functions. From a one-way function on ℓ-bit inputs, can one build a pseudorandom generator with seed length O(ℓ) that fools algorithms running in time close to the function's hardness, Vadhan's open problem 7.13 [4]?
  6. Checking the logspace claim. Do the explicit compiler and running-time bounds claimed in the L = RL = BPL manuscript, which its Lean target does not state, hold as written [9]?

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Impagliazzo, R. & Wigderson, A. (1997). P = BPP if E requires exponential circuits: derandomizing the XOR lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC '97), 220–229. 10.1145/258533.258590 · Checked 15 Oct 2026
  2. Agrawal, M., Kayal, N. & Saxena, N. (2004). PRIMES is in P. Annals of Mathematics 160(2), 781–793. 10.4007/annals.2004.160.781 · Checked 15 Oct 2026
  3. Kabanets, V. & Impagliazzo, R. (2004). Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity 13(1–2), 1–46. 10.1007/s00037-004-0182-6 · Checked 15 Oct 2026
  4. Vadhan, S. P. (2012). Pseudorandomness. Foundations and Trends in Theoretical Computer Science 7(1–3), 1–336. 10.1561/0400000010 · Checked 15 Oct 2026
  5. Aaronson, S. (2016). P =? NP. In Open Problems in Mathematics, Springer, 1–122. 10.1007/978-3-319-32162-2_1 · Checked 15 Oct 2026
  6. Doron, D., Moshkovitz, D., Oh, J. & Zuckerman, D. (2022). Nearly optimal pseudorandomness from hardness. Journal of the ACM 69(6), 1–55. Conference version in FOCS 2020. 10.1145/3555307 · Checked 15 Oct 2026
  7. Chen, L. & Tell, R. (2024). Hardness vs. randomness, revised: uniform, non-black-box, and instance-wise. SIAM Journal on Computing, FOCS21-323–FOCS21-392 (published online 4 December 2024). Conference version in FOCS 2021. 10.1137/22m1475491 · Checked 15 Oct 2026
  8. Limaye, N., Srinivasan, S. & Tavenas, S. (2025). Superpolynomial lower bounds against low-depth algebraic circuits. Journal of the ACM 72(4), 1–35. Conference version in FOCS 2021. 10.1145/3734215 · Checked 15 Oct 2026
  9. OpenAI (2026). Exact derandomization of logarithmic space: L = RL = BPL. OpenAI Math Release preprint, manuscript dated 23 September 2026, released 6 October 2026, with the manuscript of result family 142, "Deterministic Polynomial Factorization over Prime Fields" (dated 4 October 2026). Source · Checked 15 Oct 2026
  10. Aaronson, S. (2026). The Mathocalypse. Shtetl-Optimized, 7 October 2026 (updated 9 and 12 October). Source · Checked 15 Oct 2026
  11. Fortnow, L. (2026). Open No More. Computational Complexity blog, 7 October 2026. Source · Checked 15 Oct 2026
  12. Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 15 Oct 2026

Page reviewed 15 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Computing