# Does FNP-complete = NP-complete?

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?

• What's FSAT? What's FNP? – Yuval Filmus Oct 9 '13 at 3:35
• @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. – mdxn Oct 9 '13 at 5:47
• (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$". – mdxn Oct 9 '13 at 5:56
• Yuval: FSAT is the search problem equivalent of SAT, and likewise FNP is the search problem equivalent of NP. – Mike Battaglia Oct 9 '13 at 7:34
• You may be interested in “NP-complete” optimization problems and Decision problems vs “real” problems that aren't yes-or-no. – Raphael Oct 9 '13 at 12:48