|
Published Articles >> Table of Contents >> Abstract
19th Annual IEEE Conference on Computational Complexity (CCC'04)
pp. 42-53
Reductions between Disjoint NP-Pairs
Christian Glasser, Universität Würzburg
Alan L. Selman, University at Buffalo
Samik Sengupta, University at Buffalo
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313791
Send link to a friend
| Abstract |
|
Razborov [Raz94] proved that existence of an optimal proof system implies existence of a many-one complete disjoint NP-pair. Köbler, Messner, and Torán [KMT03] de- fined 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 NPpair 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 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 DisjNP has a truth-table-complete disjoint NP-pair, but has no many-one- complete disjoint NP-pair.
|
 Additional Information
|
Citation:
Christian Glasser, Alan L. Selman, Samik Sengupta,
"Reductions between Disjoint NP-Pairs,"
ccc,
pp. 42-53,
19th Annual IEEE Conference on Computational Complexity (CCC'04),
2004
|
|
