A hierarchy based on output multiplicity

Ashish V. Naik, John D. Rogers, James S. Royer, Alan L. Selman

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


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 ∑P2. 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 PNP, 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.

Original languageEnglish (US)
Pages (from-to)131-157
Number of pages27
JournalTheoretical Computer Science
Issue number1
StatePublished - Oct 28 1998


  • Generic oracle
  • Multivalued functions
  • NP
  • Polynomial hierarchy
  • Random oracle
  • Refinement
  • UP

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A hierarchy based on output multiplicity'. Together they form a unique fingerprint.

Cite this