Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-088 | 17th June 2020 18:00

The Untold Story of SBP

RSS-Feed




Revision #1
Authors: Ilya Volkovich
Accepted on: 17th June 2020 18:00
Downloads: 698
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 study the relations between these classes further, partially answering some open questions posed in \cite{BGM06}.



Changes to previous version:

Title change. Addressing some comments, extending the main result.


Paper:

TR18-088 | 24th April 2018 04:12

A story of AM and Unique-SAT





TR18-088
Authors: Ilya Volkovich
Publication: 1st May 2018 22:01
Downloads: 1888
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