Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > RANDOMIZED COMPLEXITY THEORY:
Reports tagged with Randomized Complexity Theory:
TR18-088 | 24th April 2018
Ilya Volkovich

#### A story of AM and Unique-SAT

Revisions: 1

In the seminal work of \cite{Babai85}, Babai have introduced \emph{Arthur-Merlin Protocols} and in particular the complexity classes $MA$ and $AM$ as randomized extensions of the class $NP$. While it is easy to see that $NP \subseteq MA \subseteq AM$, it has been a long standing open question whether these classes ... more >>>

ISSN 1433-8092 | Imprint