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