Classes of Representable Disjoint NP-Pairs
Classes of Representable Disjoint NP-Pairs
Olaf Beyersdorff
Abstract:
For a propositional 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 canonical NP-pairs associated with 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: dnpp_tcs_final.pdf
Abstract:
For a propositional 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 canonical NP-pairs associated with 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: dnpp_tcs_final.pdf
zuletzt geändert:
10.10.07
SK
Document Actions
Persönliche Werkzeuge
- Sie sind nicht eingeloggt.
- Log in
Deutsch
English