Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-024 | 18th February 2006 00:00

Inverting onto functions might not be hard


Authors: Harry Burhman, Lance Fortnow, Michal Koucky, John Rogers, Nikolay Vereshchagin
Publication: 24th February 2006 03:42
Downloads: 3121


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.

ISSN 1433-8092 | Imprint