A refinement of a partial multivalued function f is a function g that is undefined on all inputs on which f is undefined (that is, has no outputs), and on all inputs on which <f has outputs, g outputs at least one of f’s outputs and outputs no string that is not one of f’s outputs. Informally, g “thins down” f’s outputs, while on each element of f’s domain preserving at least one of f’s outputs. Hemaspaandra et al. [1] proved that if each multivalued NP function has a single-valued NP (function) refinement (indeed, if each at-most-two-valued NP function has a single-valued NP refinement) then the polynomial hierarchy collapses to ZPP^NP. This paper shows that this is in fact a strengthened base case of a more general behavior. Namely, for each k, we have the following: if each at-most-k-valued NP function has an at-most-( k - 1 )-valued NP refinement, then the polynomial hierarchy collapses to NP^NP.

The paper proves a number of other interesting results, including that, for each k, relative to a random oracle there is an at-most-k-valued NP function that has no at-most-( k - 1 )-valued NP refinement. It also gives the first valid published proof that UP ≠ NP relative to a random oracle, resolving a decade of confusion on that issue.