TR06-024 Authors: Harry Burhman, Lance Fortnow, Michal Koucky, John Rogers, Nikolay Vereshchagin

Publication: 24th February 2006 03:42

Downloads: 3117

Keywords:

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.