Reductions between disjoint NP-pairs
Christian Glaßer, Alan L. Selman, Samik Sengupta · 2004
Razborov (1994) proved that existence of an optimal proof system implies existence of a many-one complete disjoint NP-pair. Kobler, Messner, and Toran (2003) defined a stronger form of many-one reduction and claimed to improve Razborov's result by showing under the same assumption that there is a strongly many-one complete disjoint NP-pair. Here we show that the two results are equivalent. More generally, 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 /spl cup/ B, then all queries belong to C /spl cup/ D. We prove under the reasonable assumption UP /spl cap/ 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 DisjNP has a truth-table-complete disjoint NP-pair, but has no many-one- complete disjoint NP-pair.