ECCC-Report TR06-024https://eccc.weizmann.ac.il/report/2006/024Comments and Revisions published for TR06-024en-usFri, 24 Feb 2006 03:42:20 +0200
Paper TR06-024
| Inverting onto functions might not be hard |
Harry Burhman,
Lance Fortnow,
Michal Koucky,
John Rogers,
Nikolay Vereshchagin
https://eccc.weizmann.ac.il/report/2006/024The 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.
Fri, 24 Feb 2006 03:42:20 +0200https://eccc.weizmann.ac.il/report/2006/024