Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JOHN ROGERS:
All reports by Author John Rogers:

TR06-024 | 18th February 2006
Harry Burhman, Lance Fortnow, Michal Koucky, John Rogers, Nikolay Vereshchagin

Inverting onto functions might not be hard

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 ... more >>>




ISSN 1433-8092 | Imprint