Survey of disjoint NP-pairs and relations to propositional proof systems <s> Reductions between disjoint NP-Pairs <s> A “promise problem” is a formulation of partial decision problem. Complexity issues about promise problems arise from considerations about cracking problems for public-key cryptosystems. Using a notion of Turing reducibility between promise problems, this paper disproves a conjecture made by Even and Yacobi (1980) , that would imply nonexistence of public-key cryptosystems with NP-hard cracking problems. In its place a new conjecture is raised having the same consequence. In addition, the new conjecture implies that NP-complete sets cannot be accepted by Turing machines that have at most one accepting computation for each input word. <s> BIB001 </s> Survey of disjoint NP-pairs and relations to propositional proof systems <s> Reductions between disjoint NP-Pairs <s> A general theory of public-key cryptography is developed that is based on the mathematical framework of complexity theory. Two related approaches are taken to the development of this theory, and these approaches correspond to different but equivalent formulations of the problem of cracking a public-key cryptosystem (PKCS). The first approach is to model the cracking problem as a partial decision problem called a “promise problem.” Every NP-hard promise problem is shown to be uniformly NP-hard, and a number of results and a conjecture about promise problems are shown to be equivalent to separability assertions for sets in NP that are the natural analogues of well-known results in classical recursion theory. The conjecture, if it is true, implies nonexistence of PKCS having NP-hard cracking problems. The second approach represents the cracking problem of a PKCS as a partial computational problem directly. Using this approach, it is shown that one-way functions exist if and only if ${\text{P}} \ne {\text{UP}... <s> BIB002 </s> Survey of disjoint NP-pairs and relations to propositional proof systems <s> Reductions between disjoint NP-Pairs <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> BIB003
Since disjoint pairs are simply an equivalent formulation of promise problems, disjoint pairs easily inherit the natural notions of reducibilities that exist between promise problems [ESY84,  BIB002 . Hence, completeness and hardness notions follow naturally also. We review these here. Definition 4.1 Let (A, B) and (C, D) be disjoint pairs. The definitions tell us that for every separator of (C, D), there is a separator of (A, B) that is no more complex. In particular, if (C, D) is P-separable, then it follows immediately that (A, B) is P-separable. On the other hand, these definitions are nonuniform. Looking at (A, B)≤ pp T (C, D), for example, if S 1 is a separator of (C, D), then there is an oracle Turing machine M 1 such that the set L(M 1 , S 1 ) is a separator of (A, B). However, for a different separator S 2 of (C, D), there might be a different Turing machine M 2 so that L(M 2 , S 2 ) is a separator of (A, B). This nonuniformity makes these definitions difficult to work with. Fortunately, they have the following equivalent formulations BIB002 BIB003 . Observe that the formulation for many-one reducibility simplifies enormously.  Razborov raised the question of whether DisjNP contains complete pairs (i.e., complete disjoint NP-pairs). Although we are primarily interested in the question of whether there exist many-one complete pairs, let's pause for a moment to consider the question of whether there exist Turingcomplete pairs. Even, Selman, and Yacobi BIB001 conjectured that DisjNP does not contain a disjoint pair all of whose separators are NP-hard (i.e., ≤ p T -hard for NP.) The conjecture has strong consequences, for it implies that NP = coNP, NP = UP, and no public-key cryptosystem is NP-hard to crack BIB001 BIB002 . For example, if NP = coNP, then for every NP-complete S, the pair (S, S) is in DisjNP and all of its separators are NP-hard (since S is the only separator). We conjecture that DisjNP does not contain Turing-complete pairs, but it would be difficult to prove this, because the the latter conjecture implies the former conjecture (which in turn implies NP = coNP). Proof. Suppose there is a disjoint pair (A, B) ∈ DisjNP such that all separators are NP-hard. We claim that (A, B) is ≤ pp T -complete for DisjNP. Let (C, D) belong to DisjNP. Let S be an arbitrary separator of (A, B). Note that S is NP-hard and C ∈ NP. So C≤ Glaßer et al. BIB003 constructed an oracle relative to which Turing-complete pairs do not exist for DisjNP.