Inverting Onto Functions Might Not Be Hard
Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolay Vereshchagin · 2006
The class TFNP, dened by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially veriable 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 innite. 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 6 = UP and TFNPSAT functions are not computable in polynomial-time with a SAT oracle. 1