Unconditional derandomization of Arthur-Merlin games ★★★

Author(s): Shaltiel; Umans

\begin{problem} Prove \emph{unconditionally} that \Def[$\mathcal{AM}$]{Arthur-Merlin_protocol} $\subseteq$ \Def[$\Sigma_2$]{Polynomial_hierarchy}. \end{problem}

Keywords: Arthur-Merlin; Hitting Sets; unconditional

P vs. BPP ★★★

Author(s): Folklore

\begin{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? \end{conjecture}

Keywords: BPP; circuit complexity; pseudorandom generators

Syndicate content