Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-083 | 24th July 2005 00:00

Disjoint NP-Pairs from Propositional Proof Systems

RSS-Feed




TR05-083
Authors: Olaf Beyersdorff
Publication: 1st August 2005 17:39
Downloads: 2713
Keywords: 


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.



ISSN 1433-8092 | Imprint