ECCC-Report TR04-106https://eccc.weizmann.ac.il/report/2004/106Comments and Revisions published for TR04-106en-usFri, 26 Nov 2004 09:50:36 +0200
Paper TR04-106
| Canonical Disjoint NP-Pairs of Propositional Proof Systems |
Christian Glaßer,
Alan L. Selman,
Liyu Zhang
https://eccc.weizmann.ac.il/report/2004/106We 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.
Fri, 26 Nov 2004 09:50:36 +0200https://eccc.weizmann.ac.il/report/2004/106