License
when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1342
URN: urn:nbn:de:0030-drops-13421
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1342/

Chakaravarthy, Venkatesan T. ; Roy, Sambuddha

Finding Irrefutable Certificates for S_2^p via Arthur and Merlin

pdf-format:
Dokument 1.pdf (182 KB)


Abstract

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).

BibTeX - Entry

@InProceedings{chakaravarthy_et_al:LIPIcs:2008:1342,
  author =	{Venkatesan T. Chakaravarthy and Sambuddha Roy},
  title =	{{Finding Irrefutable Certificates for S_2^p via Arthur and Merlin}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{157--168},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1342},
  URN =		{urn:nbn:de:0030-drops-13421},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1342},
  annote =	{Keywords: Symmetric alternation, promise-AM, Karp--Lipton theorem, learning circuits}
}

Keywords: Symmetric alternation, promise-AM, Karp--Lipton theorem, learning circuits
Seminar: 25th International Symposium on Theoretical Aspects of Computer Science
Issue date: 2008
Date of publication: 06.02.2008


DROPS-Home | Fulltext Search | Imprint Published by LZI