# Is FNP = FEXPTIME if and only if NP = EXPTIME?

It is very well known that if the classes $\sf FP$ and $\sf FNP$ are equal, then also the classes $\sf P$ and $\sf NP$ are equal (see e.g. FNP on Wikipedia).

Is it also true that if $\sf FNP=FEXPTIME$ then also $\sf NP=EXPTIME$? (See the exponential time conjecture.) I did find a paper constructing real functions that are in $\sf FEXPTIME$.

• If it was trivial and direct, would you not already have a proof? Jul 1, 2014 at 12:10
• ... er, FNP is a class of relations and FEXPTIME is a class of functions. $\;$
– user12859
Jul 1, 2014 at 12:23
• @RickyDemer, aren't FP, FNP, FEXP and Fblah (for any blah) all defined formally as classes of binary relations? Moreover, a function is a binary relation anyway. Jul 1, 2014 at 13:06
• If they're defined like that then $\:$FP = FNP$\;$. $\;\;\;$ (How else could FP be defined?) $\hspace{1.67 in}$
– user12859
Jul 1, 2014 at 13:20
• @RickyDemer, FP is the class of binary relations Pxy for which y can be computed in deterministic polynomial time given x, or equivalently the subclass of FNP that can be computed in polynomial time. Jul 2, 2014 at 0:40

Yes, vacuously, since it is trivial that $\operatorname{FNP} \neq \operatorname{FEXPTIME}$, because it takes an exponentially long amount of time to give an exponentially long output.
• Presumably FEXPTIME is defined so that $|y|$ is polynomial in $|x|$. Jul 2, 2014 at 7:16