1
$\begingroup$

I can't seem to find this stated explicitly anywhere, which makes me wonder if I have it all wrong.

So first, let's say we view problems in NP as degenerate problems in FNP, where the codomain of the binary relation is the set {true, false}.

Second, FSAT is known to be FNP-complete, meaning that everything in FNP can be reduced to it in polynomial time. Also, FSAT is polynomial-time reducible to SAT, which is NP-complete, and then a SAT problem can be changed to anything else in NP-complete in polynomial time. So this shows that everything in FNP-complete can be changed to something in NP-complete in polynomial time.

So the first thing shows that NP-complete $\subset$ FNP-complete, but then the second thing shows that FNP-complete $\subset$ NP-complete, which means that NP-complete = FNP-complete.

So given that, it seems like everything in FNP can be reduced to any NP-complete problem in polynomial-time.

Am I going somewhere wrong here, or do I have this all right?

$\endgroup$
  • $\begingroup$ What's FSAT? What's FNP? $\endgroup$ – Yuval Filmus Oct 9 '13 at 3:35
  • $\begingroup$ @Mike Battaglia: You are trying to compare apples and oranges. $F_{NP}$ is a class of function problems while $NP$ is a class of decision problems. Decision classes only permit yes/no answers. Function classes involve more complicated output, such as a number. Roughly speaking, the function class $F_C$ for a decision class $C$, are function problems computable by a $C$ turing machine. It is merely the complexity of computing a class of functions. An example of a function problem would be factoring. It is not a decision problem, but can be modified to be a decision problem. $\endgroup$ – mdxn Oct 9 '13 at 5:47
  • $\begingroup$ (Continued): Note that $C$ and $F_C$ are of the same complexity at heart. A machine solving a problem in $C$ could evaluate a function in $F_C$ and output any chosen bit of it as the yes/no answer. Any language in $C$ might as well be in $F_C$, since the machine for the $F_C$ problem could output a single bit if it instead of something more complicated. I hope this helps, but in all honesty, this confusion would have been easily cleared if you just looked at Wikipedia (en.wikipedia.org/wiki/Function_problem) for "function problems", "$F_{NP}$", or "$NP$". $\endgroup$ – mdxn Oct 9 '13 at 5:56
  • $\begingroup$ Yuval: FSAT is the search problem equivalent of SAT, and likewise FNP is the search problem equivalent of NP. $\endgroup$ – Mike Battaglia Oct 9 '13 at 7:34
  • 1
    $\begingroup$ You may be interested in “NP-complete” optimization problems and Decision problems vs “real” problems that aren't yes-or-no. $\endgroup$ – Raphael Oct 9 '13 at 12:48

Your Answer

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

Browse other questions tagged or ask your own question.