Inverting Onto Functions and Polynomial Hierarchy.

The class , defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such functions are hard, for example, if is computable in polynomial-time does this imply the polynomial-time hierarchy collapses? (By computing a multivalued function in deterministic polynomial-time we mean on every input producing one of the possible values of that function on that input.) We give a relativized negative answer to this question by exhibiting an oracle under which functions are easy to compute but the polynomial-time hierarchy is infinite. We also show that relative to this same oracle, and functions are not computable in polynomial-time with an oracle. [ABSTRACT FROM AUTHOR]