Olaf Beyersdorff
Abstract: 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.