Competing Provers Yield Improved Karp--Lipton Collapse Results #.pdf

Competing Provers Yield Improved Karp–Lipton Collapse Results? Jin-Yi Cai Venkatesan T. Chakaravarthy Department of Computer Sciences, University of Wisconsin, Madison, WI 53706, USA Email: {jyc,venkat}@cs.wisc.edu Lane A. Hemaspaandra Mitsunori Ogihara Department of Computer Science, University of Rochester, Rochester, NY 14627, USA Email: {lane,ogihara}@cs.rochester.edu Technical Report URCS-TR-2001-759 September 17, 2001; revised November 2, 2002 Abstract Via competing provers, we show that if a language A is self-reducible and has polynomial-size circuits then SA2 = S2. Building on this, we strengthen the Ka?mper– AFK Theorem, namely, we prove that if NP ? (NP ∩ coNP)/poly then the polynomial hierarchy collapses to SNP∩coNP2 . We also strengthen Yap’s Theorem, namely, we prove that if NP ? coNP/poly then the polynomial hierarchy collapses to SNP2 . Under the same assumptions, the best previously known collapses were to ZPPNP and ZPPNP NP respectively ([KW98, BCK+94], building on [KL80, AFK89, Ka?m91, Yap83]). It is known that S2 ? ZPP NP [Cai01]. That result and its relativized version show that our new collapses indeed improve the previously known results. Since the Ka?mper– AFK Theorem and Yap’s Theorem are used in the literature as bridges in a variety of results—ranging from the study of unique solutions to issues of approximation—our results implicitly strengthen all those results. Keywords: Structural complexity, competing provers, nonuniform complexity, sym- metric alternation, Karp–Lipton Theorem, Yap’s Theorem, Ka?mper–AFK Theorem, lowness. 1 Proving Collapses via Competing Provers The symmetric alternation class S2 was introduced by Canetti [Can96] and Russell and Sun- daram [RS98]. In one model that captures this notion, we have two all-powerful competing provers, the Yes-Prover and the No-prover, and a polynomial-time verifier. Given an input string x, the Yes-prover and the No-prover attempt to convince the verifier of x ∈ L and of x 6∈ L, respectiv