Classes of Representable Disjoint NP-Pairs
Olaf Beyersdorff
Abstract:
For a propositional proof system P we introduce the complexity class
DNPP(P) of all disjoint NP-pairs for which the disjointness of the pair
is efficiently provable in the proof system P. We exhibit structural
properties of proof systems which make canonical NP-pairs associated
with these proof systems hard or complete for DNPP(P). Moreover, we
demonstrate that non-equivalent proof systems can have equivalent
canonical pairs and that depending on the properties of the proof
systems different scenarios for DNPP(P) and the reductions between the
canonical pairs exist.
PDF: dnpp_tcs_final.pdf