circuit complexity


P vs. BPP ★★★

Author(s): Folklore

Conjecture   Can all problems that can be computed by a probabilistic Turing machine (with error probability < 1/3) in polynomial time be solved by a deterministic Turing machine in polynomial time? That is, does P = BPP?

Keywords: BPP; circuit complexity; pseudorandom generators

Syndicate content