This paper focuses on complexity classes of partial functions that are
computed in polynomial time with oracles in NPMV, the class of all mu
ltivalued partial functions that are computable nondeterministically i
n polynomial time. Concerning deterministic polynomial-time reducibili
ties, it is shown that 1. a multivalued partial function is polynomial
-time computable with k adaptive queries to NPMV if and only if it is
polynomial-time computable via 2(k) - 1 nonadaptive queries to NPMV; 2
. a characteristic function is polynomial-time computable with k adapt
ive queries to NPMV if and only if it is polynomial-time computable wi
th k adaptive queries to NP; 3. unless the Boolean hierarchy collapses
, for every k, Ic adaptive (nonadaptive) queries to NPMV are different
than k + 1 adaptive (nonadaptive) queries to NPMV. Nondeterministic r
educibilities, lowness, and the difference hierarchy over NPMV are als
o studied. The difference hierarchy for partial functions does not col
lapse unless the Boolean hierarchy collapses, but, surprisingly, the l
evels of the difference and bounded query hierarchies do not interleav
e (as is the case for sets) unless the polynomial hierarchy collapses.