Classes of representable disjoint NP-pairs

Abstract: For a propositional proof system we introduce the complexity class of all disjoint -pairs for which the disjointness of the pair is efficiently provable in the proof system . We exhibit structural properties of proof systems which make canonical -pairs associated with these proof systems hard or complete for . 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 and the reductions between the canonical pairs exist. [Copyright &y& Elsevier]