In computational complexity theory, the complexity class FNP is the function problem extension of the decision problem class NP. The name is a bit of a misnomer, since technically it is a class of binary relations, not functions, as the following formal definition explains: In computer science, computational complexity theory is the branch of the theory of computation that studies the complexity, or efficiency, of solving computational problems. ... In computational complexity theory, a complexity class is a set of problems of related complexity. ... In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO. Notable examples include the traveling salesman problem which asks for the route taken by the salesman, and the integer factorization problem... In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ... In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ... In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ...

A binary relation P(x,y) is in FNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(x,y) holds given both x and y.

The job of an FNP algorithm is to establish, given an x, whether there exists a y such that P(x,y) holds, and if so, give one possible value for that y. See FP for an explanation of the distinction between FP and FNP. There is an NP language directly corresponding to every FNP relation, sometimes called the decision problem induced by or corresponding to said FNP relation. It is the language formed by taking all the x for which P(x,y) holds given some y; however, there may be more than one FNP relation for a particular decision problem. In computational complexity theory, the complexity class FP is the set of function problems which can be solved by a deterministic Turing machine in polynomial time; it is the function problem version of the decision problem class P. Roughly speaking, it is the class of functions that can be efficiently...

Many problems in NP, including many NP-complete problems, ask whether a particular object exists, such as a satisfying assignment, a graph coloring, or a clique of a certain size. The FNP versions of these problems ask not only if it exists but what its value is if it does. This means that the FNP version of every NP-complete problem is NP-hard. Bellare and Goldwasser showed in 1991 using some standard assumptions that there exist NP-complete problems such that their FNP versions are not self-reducible, implying that they are harder than their corresponding decision problem. In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

FP = FNP if and only if P = NP. Diagram of complexity classes provided that P ≠ NP. If P = NP, then all three classes are equal. ...

References

• M. Bellare and S. Goldwasser. The complexity of decision versus search. SIAM Journal on Computing, Vol. 23, No. 1, February 1994.
• Complexity Zoo: FNP