A hierarchy based on output multiplicity

The class NPkV 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 NPkV, 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. If for any k > 1, the class NPkV collapses into the class NP(k - 1)V, then the polynomial hierarchy collapses to ∑^P₂. 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. 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.