__
TR05-083 | 24th July 2005 00:00
__

#### Disjoint NP-Pairs from Propositional Proof Systems

**Abstract:**
For a 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 the

previously defined canonical NP-pairs of 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.