Home » Subject » Theoretical Comp. Sci. » Complexity

Derandomization


Theoretical Comp. Sci. » Complexity » Derandomization

Unconditional derandomization of Arthur-Merlin games ★★★

Author(s): Shaltiel; Umans

Problem   Prove unconditionally that $ \mathcal{AM} $ $ \subseteq $ $ \Sigma_2 $.

Keywords: Arthur-Merlin; Hitting Sets; unconditional

Posted by ormeir
updated July 16th, 2007
add new comment
Theoretical Comp. Sci. » Complexity » Derandomization

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

Posted by Charles R Great...
updated June 14th, 2013
add new comment

Note: Resolved problems from this section may be found in Solved problems.


Syndicate content