About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STACS 2008
Conference paper
Finding irrefutable certificates for S2p via Arthur and Merlin
Abstract
We show that S2p ⊆ PPrAM, where S2p 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 FPPrAM algorithm for finding a small set of "collectively irrefutable certificates" of a given S2-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 S2p ⊆ ZPPNP [5, 14]. Under the same hypothesis, we show that PH collapses to PPrMA. We also describe and FPprMAlearning polynomial size circuits for SAT, assuming such circuits exist. For the same problem, the previously best known result was a ZPPNP algorithm [4].