10.4230/LIPICS.STACS.2008.1342
Chakaravarthy, Venkatesan T.
Venkatesan T.
Chakaravarthy
Roy, Sambuddha
Sambuddha
Roy
Finding Irrefutable Certificates for S_2^p via Arthur and Merlin
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Article
Symmetric alternation
promise-AM
Karp--Lipton theorem
learning circuits
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
2008
2008-02-06
2008-02-06
2008-02-06
en
urn:nbn:de:0030-drops-13421
10.4230/LIPIcs.STACS.2008
978-3-939897-06-4
1868-8969
10.4230/LIPIcs.STACS.2008
LIPIcs, Volume 1, STACS 2008
25th International Symposium on Theoretical Aspects of Computer Science
2013
1
15
157
168
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
1
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
186648 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
We show that $S_2^psubseteq P^{prAM}$, where $S_2^p$ is the
symmetric alternation class and $prAM$ refers to the promise
version of the Arthur-Merlin class $AM$. This is derived as a
consequence of our main result that presents an $FP^{prAM}$
algorithm for finding a small set of ``collectively irrefutable
certificates'' of a given $S_2$-type matrix. The main result also
yields some new consequences of the hypothesis that $NP$ has
polynomial size circuits. It is known that the above hypothesis
implies a collapse of the polynomial time hierarchy ($PH$) to
$S_2^psubseteq ZPP^{NP}$ (Cai 2007, K"obler and Watanabe 1998).
Under the same hypothesis, we show that $PH$ collapses to
$P^{prMA}$. We also describe an $FP^{prMA}$ algorithm for learning
polynomial size circuits for $SAT$, assuming such circuits exist.
For the same problem, the previously best known result was a
$ZPP^{NP}$ algorithm (Bshouty et al. 1996).
LIPIcs, Vol. 1, 25th International Symposium on Theoretical Aspects of Computer Science, pages 157-168