2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ If it was trivial and direct, would you not already have a proof? $\endgroup$
    – Raphael
    Jul 1, 2014 at 12:10
  • $\begingroup$ ... er, FNP is a class of relations and FEXPTIME is a class of functions. $\;$ $\endgroup$
    – user12859
    Jul 1, 2014 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$ Jul 1, 2014 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, 2014 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$ Jul 2, 2014 at 0:40

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Presumably FEXPTIME is defined so that $|y|$ is polynomial in $|x|$. $\endgroup$ Jul 2, 2014 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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