Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-027 | 21st April 2003 00:00

Reductions between Disjoint NP-Pairs


Authors: Christian Gla├čer, Alan L. Selman, Samik Sengupta
Publication: 23rd April 2003 14:57
Downloads: 1411


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 {\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.

ISSN 1433-8092 | Imprint