Survey of disjoint NP-pairs and relations to propositional proof systems <s> Uniform Enumerability <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> BIB001 </s> Survey of disjoint NP-pairs and relations to propositional proof systems <s> Uniform Enumerability <s> A polynomial time computable function h : Σ* → Σ* whose range is a set L is called a proof system for L. In this setting, an h-proof for x ∈ L is just a string w with h(w) = x. Cook and Reckhow defined this concept in [13], and in order to compare the relative strength of different proof systems for the set TAUT of tautologies in propositional logic, they considered the notion of p-simulation. Intuitively, a proof system h' p-simulates h if any h-proof w can be translated in polynomial time into an h'-proof w' for h(w). We also consider the related notion of simulation between proof systems where it is only required that for any h-proof w there exists an h'-proof w' whose size is polynomially bounded in the size of w. A proof system is called (p-)optimal for a set L if it (p-)simulates every other proof system for L. The question whether p-optimal or optimal proof systems for TAUT exist is an important one in the field. In this paper we show a close connection between the existence of (p-)optimal proof systems and the existence of complete problems for certain promise complexity classes like UP, NP ∩ Sparse, RP or BPP. For this we introduce the notion of a test set for a promise class C and prove that C has a many-one complete set if and only if C has a test set T with a p-optimal proof system. If in addition the machines defining a promise class have a certain ability to guess proofs, then the existence of a p-optimal proof system for T can be replaced by the presumably weaker assumption that T has an optimal proof system. Strengthening a result from Krajicek and Pudlak [20], we also give sufficient conditions for the existence of optimal and p-optimal proof systems. <s> BIB002 </s> Survey of disjoint NP-pairs and relations to propositional proof systems <s> Uniform Enumerability <s> We consider some problems about pairs of disjoint NP sets. The theory of these sets with a natural concept of reducibility is, on the one hand, closely related to the theory of proof systems for propositional calculus, and, on the other, it resembles the theory of NP completeness. Furthermore, such pairs are important in cryptography. Among others, we prove that the Broken Mosquito Screen pair of disjoint NP sets can be polynomially reduced to Clique-Coloring pair and thus is polynomially separable and we show that the pair of disjoint NP sets canonically associated with the Resolution proof system is symmetric. <s> BIB003 </s> Survey of disjoint NP-pairs and relations to propositional proof systems <s> Uniform Enumerability <s> Disjoint NP-pairs are pairs (A, B) of nonempty, disjoint sets in NP. We prove that all of the following assertions are equivalent: There is a many-one complete disjoint NP-pair; there is a strongly many-one complete disjoint NP-pair; there is a Turing complete disjoint NP-pair such that all reductions are smart reductions; there is a complete disjoint NP-pair for one-to-one, invertible reductions; the class of all disjoint NP-pairs is uniformly enumerable. Let A, B, C, and D be nonempty sets belonging to NP. A smart reduction between the disjoint NP-pairs (A, B) and (C, D) is a Turing reduction with the additional property that if the input belongs to A ∪ B, then all queries belong to C ∪ D. We prove under the reasonable assumption that UP ∩ co-UP has a P-bi-immune set that there exist disjoint NP-pairs (A, B) and (C, D) such that (A, B) is truth-table reducible to (C, D), but there is no smart reduction between them. This paper contains several additional separations of reductions between disjoint NP-pairs. We exhibit an oracle relative to which DistNP has a truth-table-complete disjoint NP-pair, but has no many-one-complete disjoint NP-pair. <s> BIB004
In this section we describe some recent results of Glaßer, Selman, and Sengupta [GSS04] on reductions between disjoint NP-pairs. The main result is a list of equivalent statements to the assertion that there exists a many-one complete disjoint NP-pair, which, taken together, strongly suggests that the assertion does not hold. We begin our exposition with the following definition of strongly many-one reductions, as defined by Köbler, Meßner, and Torán BIB002 . Whereas Razborov proved that existence of an optimal proof system implies existence of a many-one complete disjoint NP-pair, Köbler, Meßner, and Torán proved with the same hypothesis existence of a complete disjoint NP-pair with respect to strongly many-one reductions. In particular, the result of Glaßer, Selman, and Sengupta shows that these results of Razborov and Köbler, Meßner, and Torán are equivalent. That is, there exists a many-one complete disjoint NP-pair if and only if there exists a complete disjoint NP-pair with respect to strongly many-one reductions. Nevertheless, it is apparently true that the "stronger reduction" really is stronger. This is easy to see if we permit disjoint NP-pairs whose components are finite sets. However, for pairs whose components are infinite and coinfinite, strongly many-one reductions are identical to many-one reductions if and only if P = NP. We show this result now: Given any string x, it can be determined whether x ∈ A, x ∈ B, or x ∈ A ∪ B, and x can be mapped appropriately to some fixed string in C, D, or C ∪ D. Therefore, (A, B)≤ pp sm (C, D). For the other direction, consider the clique-coloring pair (C 1 , C 2 ) such that and C 2 = { G, k G has a coloring with k − 1 colors}. This is a disjoint NP-pair, and is known to be P-separable  BIB003 . Let S be the separator that is in P. Note that (C 1 , C 2 )≤ pp m (S, S) via the identity function. (Note that this reduction is also invertible.) Let C = { G, 3 G is a cycle of odd length with at least 5 vertices}. Let S 1 = S − C and S 2 = S − C. Both S 1 and S 2 are in P. Since any odd cycle with at least 5 vertices is not 2-colorable, and does not contain any clique of size 3, C ∩ C 1 = ∅, and C ∩ C 2 = ∅. Hence C 1 and C 2 are in P. This is impossible, since NP = P, and C 1 and C 2 are NP-complete. Thus, (C 1 , C 2 ) ≤ pp sm (S 1 , S 2 ). Next we mention smart reductions. Grollmann and Selman BIB001  The following theorem is a slight simplification of the main result of Glaßer, Selman, and Sengupta BIB004 . Theorem 6.5 The following are equivalent. 1. There is a ≤ pp m -complete disjoint NP-pair. 2. There is a ≤ pp sm -complete disjoint NP-pair. 3. There is a smart ≤ pp T -complete disjoint NP-pair.