A hierarchy based on output multiplicity
Ashish V. Naik, John D. Rogers, James S. Royer, Alan L. Selman · Theoretical Computer Science · 1998
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.