Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Disjoint NP-Pairs from Propositional Proof Systems
verfasst von : Olaf Beyersdorff
Erschienen in: Theory and Applications of Models of Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.