ECCC-Report TR03-027https://eccc.weizmann.ac.il/report/2003/027Comments and Revisions published for TR03-027en-usWed, 23 Apr 2003 14:57:06 +0300
Paper TR03-027
| Reductions between Disjoint NP-Pairs |
Christian Glaßer,
Alan L. Selman,
Samik Sengupta
https://eccc.weizmann.ac.il/report/2003/027We 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 {\em 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 \cup B$, then all queries belong to
$C \cup D$. We prove
under the reasonable assumption
$\mathrm{UP} \cap \mathrm{co}\mbox{-}\mathrm{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.
Wed, 23 Apr 2003 14:57:06 +0300https://eccc.weizmann.ac.il/report/2003/027