One theme in complexity theory is to show that seemingly different, interesting questions in fact stand or fall together. This paper skillfully does that for the issue of whether complete disjoint nondeterministic polynomial (NP) pairs exist. In particular, a pair of sets that are both in NP, and that are disjoint, is said to be a disjoint NP-pair. Reductions, of various sorts, between disjoint NP-pairs can be defined in the standard natural way that is used to link promise-problem-type objects.

This paper proves that the existence of &agr; -complete disjoint NP-pairs for various reduction types &agr; stands or falls together, and the paper extends the characterization further to embrace issues of the existence of uniform enumerations and the existence of complete functions for the long-studied multivalued function class NPSV. The paper also proves both conditional and oracle separations.