Survey of disjoint NP-pairs and relations to propositional proof systems <s> Proof. <s> Abstract There exists an oracle, relative to which, P ≠ NP, and each of the following properties hold: 1. (i)All Σ 2 P -complete sets are p-isomorphic; 2. (ii)P-inseparable pairs of sets in NP do not exist; 3. (iii)Intractable public-key cryptosystems do not exist; 4. (iv)NP-complete sets are closed under union of disjoint sets. Remarkably, these properties all follow from one oracle construction. Namely, we prove that there is an oracle A such that every two disjoint sets in NP A are P-separable, and Σ 2 P = U DTIME(2 P )| p is a polynomial. Additional related relativization results are presented also. <s> BIB001 </s> Survey of disjoint NP-pairs and relations to propositional proof systems <s> Proof. <s> We study the question of whether the class DisNP of disjoint pairs (A, B) of NP-sets contains a complete pair. The question relates to the question of whether optimal proof systems exist, and we relate it to the previously studied question of whether there exists a disjoint pair of NP-sets that is NP-hard. We show under reasonable hypotheses that nonsymmetric disjoint NP-pairs exist, which provide additional evidence for the existence of P-inseparable disjoint NP-pairs. We construct an oracle relative to which the class of disjoint NP-pairs does not have a complete pair, an oracle relative to which optimal proof systems exist, hence complete pairs exist, but no pair is NP-hard, and an oracle relative to which complete pairs exist, but optimal proof systems do not exist. <s> BIB002 </s> Survey of disjoint NP-pairs and relations to propositional proof systems <s> Proof. <s> 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. We show that this degree structure is not superficial: Assuming there exist P-inseparable disjoint NP-pairs, every countable distributive lattice can be embedded into every interval of polynomial NP-degrees of disjoint pairs by maps that preserve the least and greatest element, respectively. As one consequence of this embedding, under the same assumption, 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. <s> BIB003
Suppose that f is an optimal proof system. Let (A, B) be an arbitrary disjoint NPpair. By Theorem 5.2, let g be a proof system such that (A, B)≡ Also, we state the following corollary. It is convenient for us to define the Turing-degree of a pair (A, B) ∈ DisjNP as follows: So the Turing-degree of (A, B) is the class of pairs that are equivalent to (A, B) with respect to Turing reductions. In a canonical way, Turing reductions extend from pairs to Turing-degrees: The degree structure of disjoint NP-pairs is the structure of the partial ordering ({d (A, B) (A, B) ∈ DisjNP}, ≤ pp T ). Corollary 5.6 Disjoint NP-pairs and canonical pairs for proof systems have identical degree structure. Every disjoint NP-pair we believe to be P-inseparable is many-one equivalent to some canonical pair that is also P-inseparable. We cannot prove that P-inseparable pairs exist, but there is evidence for their existence, for example, if P = UP or if P = NP ∩ coNP. On the other hand, the hypothesis that P = NP does not seem to be sufficient to obtain P-inseparable disjoint NP-pairs. Homer and Selman BIB001 constructed an oracle relative to which P = NP and all disjoint NP-pairs are P-separable. Glaßer et al. BIB002 constructed an oracle O 1 relative to which optimal proof systems exist, and therefore, relative to which many-one complete disjoint NP-pairs exist. Also, they constructed an oracle O 2 relative to which many-one complete disjoint NP-pairs exist, but optimal proof systems do not exist. So relative to this oracle, the converse of Corollary 5.5 does not hold. Relative to O 2 , there is a propositional proof system f whose canonical pair is complete, but f is not optimal. Hence, there is a propositional proof system g such that the canonical pair of g manyone reduces to the canonical pair of f , but f does not simulate g. The results of this section (Proposition 5.1, Theorem 5.2, and Corollary 5.6) present tight connections between disjoint NPpairs and propositional proof systems. Nevertheless, relative to this oracle, the relationship is not as tight as one might hope for. In light of Corollary 5.6, we should try to understand the degree structure of DisjNP. Glaßer, Selman, and Zhang BIB003 prove that between any two comparable and inequivalent disjoint NPpairs (A, B) and (C, D) there exist P-inseparable, incomparable NP-pairs (E, F ) and (G, H) whose degrees lie strictly between (A, B) and (C, D). Their result is an analogue of Ladner's result for NP  . The proof is based on Schöning's formulation  and uses techniques of Regan   . Thus, assuming that P-inseparable disjoint NP-pairs exist, the class DisjNP has a rich, dense, degree structure-and each of these degrees contains a canonical pair. Observe that the premise of the following theorem is true as long as there exist P-inseparable disjoint NP-pairs. H) between (A, B) and (C, D) such that E, F , G, and H are infinite. Precisely, the following properties hold: Messner   unconditionally proved the existence of propositional proof systems f and g such that f does not simulate g and g does not simulate f . Further he shows that the simulation order of propositional proof systems is dense. However, from this we cannot conclude a dense degree structure for disjoint NP-pairs. There exist infinite, strictly increasing chains of propositional proof systems (using simulation as the order relation ≤) such that all canonical pairs of these proofs systems belong to the same many-one degree of disjoint NP-pairs.