Survey of disjoint NP-pairs and relations to propositional proof systems <s> DisjNP is uniformly enumerable. <s> This paper develops techniques for studying complexity classes that are not covered by known recursive enumerations of machines. Often, counting classes, probabilistic classes, and intersection classes lack such enumerations. Concentrating on the counting class UP, we show that there are relativizations for which UPA has no complete languages and other relativizations for which PB ≠ UPB ≠ NPB and UPB has complete languages. Among other results we show that P ≠ UP if and only if there exists a set S in P of Boolean formulas with at most one satisfying assignment such that S ∩ SAT is not in P. P ≠ UP ∩ coUP if and only if there exists a set S in P of uniquely satisfiable Boolean formulas such that no polynomial-time machine can compute the solutions for the formulas in S. If UP has complete languages then there exists a set R in P of Boolean formulas with at most one satisfying assignment so that SAT ∩ R is complete for UP. Finally, we indicate the wide applicability of our techniques to counting and probabilistic classes by using them to examine the probabilistic class BPP. There is a relativized world where BPPA has no complete languages. If BPP has complete languages then it has a complete language of the form B ∩ MAJORITY, where B ∈ P and MAJORITY = {f | f is true for at least half of all assignments} is the canonical PP-complete set. <s> BIB001 </s> Survey of disjoint NP-pairs and relations to propositional proof systems <s> DisjNP is uniformly enumerable. <s> In this paper we develop a connection between optimal propositional proof systems and structural complexity theory--specifically, there exists an optimal propositional proof system if and only if there is a suitable recursive presentation of the class of all easy (polynomial time recognizable) subsets of TAUT. As a corollary we obtain the result that if there does not exist an optimal propositional proof system, then for every theory T there exists an easy subset of TAUT which is not T-provably easy. <s> BIB002
There is a long history of equating having complete sets with uniform enumerations. Hartmanis and Hemachandra BIB001 , for example, proved this for the class UP, and it holds as well for NP ∩ co-NP and BPP. More recently, Sadowski BIB002 proved that there exists an optimal propositional proof system if and only if the class of all easy subsets of TAUT is uniformly enumerable. 2 It seems inconceivable that there would exist a total computable function that lists exactly the disjoint NPpairs, and that is why we don't believe that many-one complete disjoint NP-pairs exist, and hence, don't believe that optimal proof systems exist. The most interesting direction of the proof is to show that if there exists a many-one complete disjoint NP-pair, then DisjNP is uniformly enumerable. We sketch this direction now: Let (A, B) be a ≤ pp m -complete disjoint pair. Let N A and N B be NP-machines that accept A and B, respectively. Let {f i } i be an effective enumeration of polynomial-time computable functions. Input to the enumerator is a number encoding a triple i, j, k . Output is a pair a, b to be described. Given i, j, k , we define nondeterministic Turing machines N 1 and N 2 as follows. On input x, N 1 computes f i (x) = q and then simulates both N A (q) and N B (q). At most one of these accepts. N 1 accepts x if x ∈ L(N j ) and q ∈ L(N A ). N 2 is defined similarly, except that N 2 accepts x if x ∈ L(N k ) and q ∈ L(N B ). 