FNP (complexity)
|
|
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:
- 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 establish, given an x, whether there exists a y such that P(x,y) holds, and if so, 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 it. It is the language formed by taking all the x for which P(x,y) holds for some y; however, there may be more than one FNP relation for a particular decision problem.
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. Although computing this value is harder in general than determining mere existence, Bellare and Goldwasser showed in 1991 the surprising result that all FNP versions of NP-complete problems are in fact self-reducible, implying that they aren't really any harder than their corresponding decision problem (formally, there is a polynomial-time Turing reduction from the search problem to the decision problem).
FP = FNP if and only if P = NP.
References
- M. Bellare and S. Goldwasser. The complexity of decision versus search (http://citeseer.csail.mit.edu/bellare94complexity.html). MIT-LCS Technical Memo. TM-444. April 1991.
- Complexity Zoo: FNP (http://www.complexityzoo.com/#fnp)