Revision #1 Authors: Olaf Beyersdorff

Accepted on: 21st January 2005 00:00

Downloads: 2741

Keywords:

We correct a mistake in the proof of Proposition 17 and add Corollary 20

as an immediate but interesting consequence.

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.