Details

Autor(en) / Beteiligte

• Beyersdorff, Olaf

Titel

Representable Disjoint NP-Pairs

Ist Teil von

• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004, p.122-134

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

2004

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• We investigate the class of disjoint NP-pairs under different reductions. The structure of this class is intimately linked to the simulation order of propositional proof systems, and we make use of the relationship between propositional proof systems and theories of bounded arithmetic as the main tool of our analysis. Specifically we exhibit a pair which is complete under strong reductions for all disjoint NP-pairs representable in a theory. We use these pairs to explain the simulation order of NP-pairs under these reductions. As corollaries we also get simplified proofs of results obtained earlier in [3] and [5].