ContactPerson: selman@cse.buffalo.edu Remote host: selman.cse.buffalo.edu ### Begin Citation ### Do not delete this line ### %R 2004-17 %U /web/faculty/selman/degrees.ps %A Glasser, Christian %A Selman, Alan L. %A Zhang, Liyu %T Canonical Disjoint NP-Pairs of Propositional Proof Systems %D November 19, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K disjoint NP-pairs, propositional proof systems, canonical pairs, degrees %Y F.1.3 %X 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 P-inseparable disjoint pairs, there exist intermediate disjoint NP-pairs. That is, if $(A, B)$ is a P-separable disjoint NP-pair and $(C, D)$ is a P-inseparable disjoint NP-pair, then there exist P-inseparable, incomparable NP-pairs $(E, F)$ and $(G, H)$ whose degrees lie strictly between $(A, B)$ and $(C, D)$. Furthermore, between any two disjoint NP-pairs that are comparable and inequivalent, such a diamond exists.