The class TFNP, 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 TFNP is computable in polynomial-time does
this imply the polynomial-time hierarchy collapses?

We give a relativized negative answer to this question by
exhibiting an oracle under which TFNP functions are easy to
compute but the polynomial-time hierarchy is infinite.

To create the oracle, we introduce Kolmogorov-generic oracles
where the strings placed in the oracle are derived from an
exponentially long Kolmogorov-random string. We also show that
relative to this same oracle, P is not equal to UP and TFNP
functions with a SAT oracle are not computable in polynomial-time with a SAT oracle.