A hierarchy based on output multiplicity

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

Research output: Contribution to journalArticle

13 Scopus citations

Abstract

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
Volume207
Issue number1
DOIs
StatePublished - Oct 28 1998

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Naik, A. V., Rogers, J. D., Royer, J. S., & Selman, A. L. (1998). A hierarchy based on output multiplicity. Theoretical Computer Science, 207(1), 131-157. https://doi.org/10.1016/S0304-3975(98)00060-7