TY - JOUR

T1 - A hierarchy based on output multiplicity

AU - Naik, Ashish V.

AU - Rogers, John D.

AU - Royer, James S.

AU - Selman, Alan L.

N1 - Funding Information:
* Corresponding author. E-mail: [email protected]. ’ Research performed at the Department of Computer Science, University of Chicago, with support from NSF grant CCR-9253582, and at the Department of Computer Science, University at Buffalo, with support from NSF grant CCR-9400229. ’ The second author gratefully acknowledges a visiting scholar appointment to the University of Chicago that facilitated this work. 3 Research supported in part by NSF grant CCR-9522987. 4 Research supported in part by NSF grant CCR-9400229. This author presented some of the results herein in preliminary form at the Eleventh IEEE Conference on Computational Complexity.

PY - 1998/10/28

Y1 - 1998/10/28

N2 - 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.

AB - 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.

KW - Generic oracle

KW - Multivalued functions

KW - NP

KW - Polynomial hierarchy

KW - Random oracle

KW - Refinement

KW - UP

UR - http://www.scopus.com/inward/record.url?scp=0009237231&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0009237231&partnerID=8YFLogxK

U2 - 10.1016/S0304-3975(98)00060-7

DO - 10.1016/S0304-3975(98)00060-7

M3 - Article

AN - SCOPUS:0009237231

SN - 0304-3975

VL - 207

SP - 131

EP - 157

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

ER -