## 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 ∑^{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. 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 language | English (US) |
---|---|

Pages (from-to) | 131-157 |

Number of pages | 27 |

Journal | Theoretical Computer Science |

Volume | 207 |

Issue number | 1 |

DOIs | |

State | Published - Oct 28 1998 |

## Keywords

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

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science