In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
, the
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...
FNP is the
function problem
In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem. For function problems, the ou ...
extension of the
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
class
NP. The name is somewhat of a misnomer, since technically it is a class of
binary relation
In mathematics, a binary relation associates some elements of one Set (mathematics), set called the ''domain'' with some elements of another set called the ''codomain''. Precisely, a binary relation over sets X and Y is a set of ordered pairs ...
s, not functions, as the following formal definition explains:
:A binary relation P(''x'',''y''), where ''y'' is at most polynomially longer than ''x'', 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''.
This definition does not involve nondeterminism and is analogous to the verifier definition of NP.
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.
Many problems in NP, including many
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
problems, ask whether a particular object exists, such as a satisfying assignment, a
graph coloring
In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...
, or a clique of a certain size. These problems often correspond to problems in FNP that ask not only whether an object exists but what value or values such an object can have. When a FNP problem corresponds in this way to an NP-complete problem, it is
NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
. Bellare and Goldwasser showed in 1994 using some standard assumptions that there exist problems in NP such that their FNP versions are not
self-reducible, implying that they are harder than their corresponding decision problem.
For each P(''x'',''y'') in FNP, the search problem associated with P(''x'',''y'') is: given ''x'', find a ''y'' such that P(''x'',''y'') holds, or state that no such ''y'' exists. The search problem for every relation in FNP can be solved in polynomial time if and only if
P = NP. This result is usually stated as "
FP = FNP if and only if
P = NP"; however, for this statement to be true, it is necessary to redefine FP and FNP so that the members of FP and FNP are not relations, but are instead search problems associated with relations.
Reductions
Let ''P''
1 and ''P''
2 be two problems in FNP, with associated verification algorithms ''A''
1, ''A''
2. A reduction ''P''
1 and ''P''
2 is defined as two efficiently-computable functions, ''f'' and ''g'', such that
* ''f'' maps inputs ''x'' to ''P''
1 to inputs ''f''(''x'') to ''P''
2 ;
* ''g'' maps outputs ''y'' to ''P''
2 to outputs ''g''(y) to ''P''
1 ;
* For all ''x'' and ''y'': if ''A''
2(''f''(''x''),''y'') returns true, then ''A''
1(''x'', g(''y'')) returns true;
* For all ''x'': if ''A''
2(''f''(''x''),''y'') returns false for all ''y'', then ''A''
1(''x'', g(''y'')) returns false for all ''y''.
Related complexity classes
*
FP is the set of binary relations for which there is a polynomial time algorithm that, given ''x'', finds some ''y'' for which P(''x'',''y'') holds. The relation between FNP and FP is analogous to the relation between NP and P.
*
TFNP is a subset of FNP: it contains those relations in FNP for which, for every ''x'', there exists at least one ''y'' for which P(''x'',''y'') holds.
References
External links
*
{{DEFAULTSORT:Fnp (Complexity)
Complexity classes
Binary relations