2026-07-27T05:06:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1342 2024-03-06T10:32:58Z ddc:004 open_access

Finding Irrefutable Certificates for S_2^p via Arthur and Merlin Chakaravarthy, Venkatesan T. Roy, Sambuddha Symmetric alternation promise-AM Karp--Lipton theorem learning circuits 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Venkatesan T. Chakaravarthy and Sambuddha Roy 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1342 urn:nbn:de:0030-drops-13421 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1342 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode