Skip to content

Does randomness help? P versus BPP

Unsolved Research level Archive archive posted

BPP is the class of decision problems solvable by a polynomial-time randomized algorithm that answers correctly with probability at least 2/3 on every input. Is every problem in BPP solvable by a deterministic polynomial-time algorithm, that is, is P = BPP?

Posed by folklore
Like0
complexity-theoryderandomizationopen-questionrandomized-algorithms
History and references

Still open as of 2026.

Several problems once known only to have fast randomized algorithms have since been derandomized. The best known example is primality testing, placed in P by Agrawal, Kayal and Saxena in 2002. Polynomial identity testing, deciding whether an arithmetic circuit computes the zero polynomial, is the most prominent problem known to be in BPP but not known to be in P. In 1997 Impagliazzo and Wigderson showed that if some problem in the class E requires circuits of size , then P = BPP. Most researchers conjecture that P = BPP, but no unconditional proof is known.

References

Solutions 0

Nobody has posted a solution here yet. Solutions written on Problempedia are credited to the people who write them.

Discussion 0

Sign in to join the discussion