From nobody@cs.Buffalo.EDU Tue Aug  5 11:02 EDT 1997
From: nobody@cs.Buffalo.EDU
Date: Tue, 5 Aug 1997 11:01:55 -0400 (EDT)
To: techreps@cs.Buffalo.EDU
Subject: techrep: POST request
Content-Type: text
Content-Length: 1767

ContactPerson: selman@cs.buffalo.edu
Remote host: sargas.cs.buffalo.edu
Remote ident: selman
### Begin Citation ### Do not delete this line ###
%R 97-13
%U /projects/selman/multiplicity.ps
%A Naik, Ashish V.
%A Rogers, John, D.
%A Royer, James S.
%A Selman, Alan L.
%T A Hierarchy Based on Output Multiplicity
%D August 05, 1997
%I Department of Computer Science, SUNY Buffalo
%K multivavlued functions, nondeterminism, function classes, output multiplicity
%X 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 {\em output-multiplicity hierarchy\/}  
to consist of the collection of classes NP$k$V, for all positive  
integers $k \geq 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 NP$k$V collapses into the class  
    NP$(k - 1$V, then the polynomial hierarchy collapses to  
    its second level, $\Sigma_2^P$.     
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\not=\NP$.