Finding Irrefutable Certificates for $S 2^p$ via Arthur and MerlinReport as inadecuate

Finding Irrefutable Certificates for $S 2^p$ via Arthur and Merlin - Download this document for free, or read online. Document in PDF available to download.

1 India Research Laboratory Bangalore

Abstract : We show that $S 2^p\subseteq 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^p\subseteq ZPP^{NP}$ Cai 2007, Köbler 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.

Keywords : Symmetric alternation promise-AM Karp-Lipton theorem learning circuits

Author: Venkatesan Chakaravarthy - Sambuddha Roy -



Related documents