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?

Improve this question
$\endgroup$
10
  • $\begingroup$ What's FSAT? What's FNP? $\endgroup$
    – Yuval Filmus
    Oct 9, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 12:48

0

Reset to default

Your Answer

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