login/create account
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
Drupal
CSI of Charles University