Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Disjoint NP-pairs from propositional proof systems

O. Beyersdorff


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