Editing Function problem (section)

== Relationship to other complexity classes ==
Consider an arbitrary [[decision problem]] <math>L</math> in the class [[NP (complexity)|'''NP''']]. By the definition of '''NP''', each problem instance <math>x</math> that is answered 'yes' has a polynomial-size certificate <math>y</math> which serves as a proof for the 'yes' answer. Thus, the set of these tuples <math>(x,y)</math> forms a relation, representing the function problem "given <math>x</math> in <math>L</math>, find a certificate <math>y</math> for <math>x</math>". This function problem is called the ''function variant'' of <math>L</math>; it belongs to the class '''[[FNP (complexity)|FNP]]'''.

'''FNP''' can be thought of as the function class analogue of '''NP''', in that solutions of '''FNP''' problems can be efficiently (i.e., in [[polynomial time]] in terms of the length of the input) ''verified'', but not necessarily efficiently ''found''. In contrast, the class '''[[FP (complexity)|FP]]''', which can be thought of as the function class analogue of '''P''', consists of function problems whose solutions can be found in polynomial time.