Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with degrees:
TR04-106 | 19th November 2004
Christian Gla├čer, Alan L. Selman, Liyu Zhang

Canonical Disjoint NP-Pairs of Propositional Proof Systems

We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to
the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is
identical. Secondly, we show that this degree structure is not superficial: Assuming there exist ... more >>>

ISSN 1433-8092 | Imprint