TR03-027 Authors: Christian Glaßer, Alan L. Selman, Samik Sengupta

Publication: 23rd April 2003 14:57

Downloads: 2946

Keywords:

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.