Classes of representable disjoint NP-pairs
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 nonequivalent 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. (c) 2007 Elsevier B.V. All rights reserved.
disjoint np-pairs propositional proof systems