Details

Autor(en) / Beteiligte

• Cai, Jin-Yi
• Chakaravarthy, Venkatesan T.
• Hemaspaandra, Lane A.
• Ogihara, Mitsunori

Titel

Competing Provers Yield Improved Karp-Lipton Collapse Results

Ist Teil von

• Lecture notes in computer science, 2003, p.535-546

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

2003

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• Via competing provers, we show that if a language A is selfreducible and has polynomial-size circuits then SA2 = S2. Building on this, we strengthen the Kä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 ZPPNPNP respectively ([20],[6], building on [18,1,17,30]). It is known that S2 ⊆ ZPPNP [8]. That result and its relativized version show that our new collapses indeed improve the previously known results. Since the Kä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.