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. We also show that relative to this same oracle, P not equal UP and TFNP(NP) functions are not computable in polynomial-time with an NP oracle.
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.