The class NP k V consists of those partial, multivalued functions that can be computed by a nondeterministic, polynomial time-bounded transducer that has at most k distinct values on any input. We define the output-multiplicity hierarchy to consist of the collection of classes NP k V for all positive integers k ≥ 1. In this paper we investigate the strictness of the output-multiplicity hierarchy and establish three main results pertaining to this: 1. 1. If for any k > 1, the class NP k V collapses into the class NP( k − 1)V, then the polynomial hierarchy collapses to Σ 2 P . 2. 2. If the converse of the above result is true, then any proof of this converse cannot relativize. We exhibit an oracle relative to which the polynomial hierarchy collapses to P NP , but the output-multiplicity hierarchy is strict. 3. 3. Relative to a random oracle, the output-multiplicity hierarchy is strict. This result is in contrast to the still open problem of the strictness of the polynomial hierarchy relative to a random oracle. In introducing the technique for the third result we prove a related result of interest: relative to a random oracle UP ≠ NP.

We address two questions about self-reducibility-the power of adaptiveness in examiners that take advice and the relationship between random-self-reducibility and self-correctability. We first show that adaptive examiners are more powerful than nonadaptive examiners, even if the nonadaptive ones are nonuniform. Blum et al. (1993) showed that every random-self-reducible function is self-correctable. However, whether self-correctability implies random-self-reducibility is unknown. We show that, under a reasonable complexity hypothesis, there exists a self-correctable function that is not random-self-reducible. For P-sampleable distributions, however, we show that constructing a self-correctable function that is not random-self-reducible is as hard as proving that P/spl ne/PP.

We look at the hypothesis that all honest onto polynomial-time computable functions have a polynomial-time computable inverse. We show this hypothesis equivalent to several other complexity conjectures including: One can find accepting paths of nondeterministic polynomial-time Turing machines that accept /spl Sigma/*. Every total multivalued nondeterministic function has a polynomial-time computable refinement. One can compute satisfying assignments for any polynomial-time computable set of satisfiable formulae. One can convert the accepting computations of any nondeterministic Turing machine that accepts SAT to satisfying assignments. We compare these hypotheses with several other important complexity statements. We also examine the complexity of these statements where we only require a single bit instead of the entire inverse, path, etc.

We study two properties of a complexity class C-whether there exists a truth-table hard p-selective language for C, and whether polynomially-many nonadaptive queries to C can be answered by making O(log n)-many adaptive queries to C (in symbols, is PF/sub tt//sup C//spl sube/PF/sup C/[O(log n)]). We show that if there exists an NP-hard p-selective set under truth-table reductions, then PF/sub tt//sup NP//spl sube/PF/sup NP/[O(log n)]. We observe that if C/spl supe/P/sup NP/, then these two properties are equivalent. Also, we show that if there exists a truth-table complete standard-left cut in NP, then the polynomial hierarchy collapses to P/sup NP/. We prove that P=NP follows if for some k>0, the class PF/sub tt//sup NP/ is "effectively included" in PF/sup NP/[k[log n]-1].

We distinguish self-reducibility of a languageLwith the question of whether search reduces to decision forL. Results include: (i) If NE≠E, then there exists a setLin NP−P such that search reduces to decision forL, search doesnotnonadaptively reduce to decision forLandLis not self-reducible. (ii) If UE≠E, then there exists a languageL∈UP−P such that search nonadaptively reduces to decision for L, but L is not self-reducible. (iii) If UE∩co-UE≠E, then there is a disjunctive self-reducible languageL∈UP−P for which search doesnotnonadaptively reduce to decision. We prove that if NE⊈BPE, then there is a languageL∈NP−BPP such thatLis randomly self-reducible,notnonadaptively randomly self-reducible, andnotself-reducible. We obtain results concerning trade-offs in multiprover interactive proof systems and results that distinguish checkable languages from those that are nonadaptively checkable. Many of our results are proven by constructing p-selective sets. We obtain a p-selective set that isnot⩽Ptt-equivalent to any tally language, and we show that if P=PP, then every p-selective set is ⩽PT-equivalent to a tally language. Similarly, if P=NP, then every cheatable set is ⩽Pm-equivalent to a tally language. We construct a recursive p-selective tally set that isnotcheatable.

Is there an NP function that, when given a satisfiable formula as input, outputs one satisfying assignment uniquely? That is, can a nondeterministic function cull just one satisfying assignment from a possibly exponentially large collection of assignments? We show that if there is such a nondeterministic function, then the polynomial hierarchy collapses to ${\text{ZPP}}^{{\text{NP}}} $ (and thus, in particular, to ${\text{NP}}^{{\text{NP}}} $). Because the existence of such a function is known to be equivalent to the statement “every NP function has an NP refinement with unique outputs,” our result provides the strongest evidence yet that NP functions cannot be refined. We prove our result via a result of independent interest. We say that a set A is NPSV-selective (NPMV-selective) if there is a 2-ary partial NP function with unique values (a 2-ary partial NP function) that decides which of its inputs (if any) is “more likely” to belong to A; this is a nondeterministic analog of the recursion-theoretic notion of the semirecursive sets and the extant complexity-theoretic notion of P-selectivity. Our hierarchy-collapse result follows by combining the easy observation that every set in NP is NPMV-selective with the following result: If $A \in {\text{NP}}$ is NPSV-selective, then $A \in {{({\text{NP}} \cap {\text{coNP}})} / {{\text{poly}}}}$. Relatedly, we prove that if $A \in {\text{NP}}$ is NPSV-selective, then A is ${\text{Low}}_2 $. We prove that the polynomial hierarchy collapses even further, namely to NP, if all coNP sets are NPMV-selective. This follows from a more general result we prove: Every self-reducible NPMV-selective set is in NP.