Editing Function problem (section)

== Reductions and complete problems ==
Function problems can be [[Reduction (complexity)|reduced]] much like decision problems: Given function problems <math>\Pi_R</math> and <math>\Pi_S</math> we say that <math>\Pi_R</math> reduces to <math>\Pi_S</math> if there exists polynomially-time computable functions <math>f</math> and <math>g</math> such that for all instances <math>x</math> of <math>R</math> and possible solutions <math>y</math> of <math>S</math>, it holds that

*If <math>x</math> has an <math>R</math>-solution, then <math>f(x)</math> has an <math>S</math>-solution.
*<math>(f(x), y) \in S \implies (x, g(x,y)) \in R.</math>

It is therefore possible to define '''FNP-complete''' problems analogous to the NP-complete problem:

A problem <math>\Pi_R</math> is '''FNP-complete''' if every problem in '''FNP''' can be reduced to <math>\Pi_R</math>. The complexity class of '''FNP-complete''' problems is denoted by '''FNP-C''' or '''FNPC'''. Hence the problem '''FSAT''' is also an '''FNP-complete''' problem, and it holds that <math>\mathbf{P} = \mathbf{NP}</math> if and only if <math>\mathbf{FP} = \mathbf{FNP}</math>.