## Disjoint NP-pairs from propositional proof systems

O. Beyersdorff

**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.

PDF-File: Disjoint NP-pairs from
propositional proof systems