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

  • $\begingroup$ If it was trivial and direct, would you not already have a proof? $\endgroup$ – Raphael Jul 1 '14 at 12:10
  • $\begingroup$ ... er, FNP is a class of relations and FEXPTIME is a class of functions. $\;$ $\endgroup$ – user12859 Jul 1 '14 at 12:23
  • $\begingroup$ @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. $\endgroup$ – Luke Mathieson Jul 1 '14 at 13:06
  • $\begingroup$ If they're defined like that then $\:$FP = FNP$\;$. $\;\;\;$ (How else could FP be defined?) $\hspace{1.67 in}$ $\endgroup$ – user12859 Jul 1 '14 at 13:20
  • $\begingroup$ @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. $\endgroup$ – Luke Mathieson Jul 2 '14 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.

  • $\begingroup$ Presumably FEXPTIME is defined so that $|y|$ is polynomial in $|x|$. $\endgroup$ – Yuval Filmus Jul 2 '14 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.