Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-088 | 24th April 2018 04:12

A story of AM and Unique-SAT

RSS-Feed




TR18-088
Authors: Ilya Volkovich
Publication: 1st May 2018 22:01
Downloads: 162
Keywords: 


Abstract:

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 are actually different.
In \cite{BGM06}, B{\"{o}}hler et al. introduced the probabilistic class of $SBP$ and showed that $MA \subseteq SBP \subseteq AM$. Indeed, this is the only known natural complexity class that lies between $MA$ and $AM$. In this work we show that the class $AM$ collapses to $SBP$ if $UNIQUE$-$SAT$ is $NP$-hard, where $UNIQUE$-$SAT$ stands for the problem of deciding whether a Boolean formula has a unique satisfying assignment or none.



ISSN 1433-8092 | Imprint