Finding irrefutable certificates for S₂^p 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].