FNP (complexity): Difference between revisions
Jump to navigation
Jump to search
imported>Kku m link graph coloring |
No edit summary |
||
| Line 2: | Line 2: | ||
In [[computational complexity theory]], the [[complexity class]] '''FNP''' is the [[function problem]] extension of the [[decision problem]] class [[NP (complexity)|NP]]. The name is somewhat of a misnomer, since technically it is a class of [[binary relation]]s, not functions, as the following formal definition explains: | In [[computational complexity theory]], the [[complexity class]] '''FNP''' is the [[function problem]] extension of the [[decision problem]] class [[NP (complexity)|NP]]. The name is somewhat of a misnomer, since technically it is a class of [[binary relation]]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<!-- *not* nondeterministic --> polynomial time algorithm that can determine whether P(''x'',''y'') holds given both ''x'' and ''y''.<ref>[[Elaine Rich]], ''Automata, Computability and Complexity: Theory and Applications'', Prentice Hall, 2008, {{ISBN|0-13-228806-0}}, section 28.10 "The problem classes FP and FNP", pp. 689–694</ref> | :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<!-- *not* nondeterministic --> polynomial-time algorithm that can determine whether ''P''(''x'',''y'') holds given both ''x'' and ''y''.<ref>[[Elaine Rich]], ''Automata, Computability and Complexity: Theory and Applications'', Prentice Hall, 2008, {{ISBN|0-13-228806-0}}, section 28.10 "The problem classes FP and FNP", pp. 689–694</ref> | ||
This definition does not involve nondeterminism and is analogous to the verifier definition of NP. | 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 | There is an NP [[formal language|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 there exists some ''y'' such that ''P''(''x'',''y'') holds; however, there may be more than one FNP relation that induces a particular decision problem. | ||
Many problems in NP, including many [[NP-complete]] problems, | Many problems in NP, including many [[NP-complete]] problems, can be specifed by asking whether a particular object exists, such as a satisfying assignment, a [[graph coloring]], or a [[clique (graph theory)|clique]] of a certain size. These problems often correspond to relations in FNP that ask not only whether an object exists but what value or values such an object can have. When an FNP relation corresponds in this way to an NP-complete problem, the relation is [[self-reducibility|self-reducible]]. [[Mihir Bellare|Bellare]] and [[Shafi Goldwasser|Goldwasser]] showed in 1994 using some standard complexity-theoretic assumptions that there exist problems in NP such that none of their FNP versions are self-reducible, implying that they are harder than their corresponding decision problem.<ref>M. Bellare and S. Goldwasser. [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.4445 The complexity of decision versus search]. [[SIAM Journal on Computing]], Vol. 23, No. 1, February 1994. | ||
</ref> | </ref> | ||
For each | For each ''P'' in FNP, the search problem associated with ''P'' 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 deterministically in polynomial time if and only if [[P = NP problem|P = NP]]. This result is usually stated as "[[FP (complexity)|FP]] = FNP if and only if [[P = NP problem|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 == | == Reductions == | ||
Let ''P''<sub>1</sub> and ''P''<sub>2</sub> be two problems in FNP, with associated verification algorithms ''A''<sub>1</sub>, ''A''<sub>2</sub>. A reduction ''P''<sub>1</sub> and ''P''<sub>2</sub> is defined as two | Let ''P''<sub>1</sub> and ''P''<sub>2</sub> be two problems in FNP, with associated verification algorithms ''A''<sub>1</sub>, ''A''<sub>2</sub>. A reduction ''P''<sub>1</sub> and ''P''<sub>2</sub> is defined as two polynomial-time computable functions, ''f'' and ''g'', such that<ref>{{Cite web|last=Daskalakis|first=Costis|authorlink = Constantinos Daskalakis|date=2015|title=22. PPAD|url=https://www.youtube.com/watch?v=TUbfCY_8Dzs|archive-url=|archive-date=|access-date=|website=MIT OpenCourseWare}}</ref> | ||
* ''f'' maps inputs ''x'' | * ''f'' maps inputs ''x'' of ''P''<sub>1</sub> to inputs ''f''(''x'') of ''P''<sub>2</sub> ; | ||
* ''g'' maps outputs ''y'' | * ''g'' maps outputs ''y'' of ''P''<sub>2</sub> to outputs ''g''(y) of ''P''<sub>1</sub> ; | ||
* For all ''x'' and ''y'': if ''A''<sub>2</sub>(''f''(''x''),''y'') returns true, then ''A''<sub>1</sub>(''x'', g(''y'')) returns true; | * For all ''x'' and ''y'': if ''A''<sub>2</sub>(''f''(''x''),''y'') returns true, then ''A''<sub>1</sub>(''x'', ''g''(''y'')) returns true; | ||
* For all ''x'': if ''A''<sub>2</sub>(''f''(''x''),''y'') returns false for all ''y'', then ''A''<sub>1</sub>(''x'', g(''y'')) returns false for all ''y''. | * For all ''x'': if ''A''<sub>2</sub>(''f''(''x''),''y'') returns false for all ''y'', then ''A''<sub>1</sub>(''x'', ''g''(''y'')) returns false for all ''y''. | ||
== Related complexity classes == | == Related complexity classes == | ||
* [[FP (complexity)|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. | * [[FP (complexity)|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. | *[[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 == | == References == | ||
Latest revision as of 16:58, 5 December 2025
Template:Short description In computational complexity theory, the complexity class FNP is the function problem extension of the decision problem class NP. The name is somewhat 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), 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.[1]
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 there exists some y such that P(x,y) holds; however, there may be more than one FNP relation that induces a particular decision problem.
Many problems in NP, including many NP-complete problems, can be specifed by asking whether a particular object exists, such as a satisfying assignment, a graph coloring, or a clique of a certain size. These problems often correspond to relations in FNP that ask not only whether an object exists but what value or values such an object can have. When an FNP relation corresponds in this way to an NP-complete problem, the relation is self-reducible. Bellare and Goldwasser showed in 1994 using some standard complexity-theoretic assumptions that there exist problems in NP such that none of their FNP versions are self-reducible, implying that they are harder than their corresponding decision problem.[2]
For each P in FNP, the search problem associated with P 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 deterministically 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 P1 and P2 be two problems in FNP, with associated verification algorithms A1, A2. A reduction P1 and P2 is defined as two polynomial-time computable functions, f and g, such that[3]
- f maps inputs x of P1 to inputs f(x) of P2 ;
- g maps outputs y of P2 to outputs g(y) of P1 ;
- For all x and y: if A2(f(x),y) returns true, then A1(x, g(y)) returns true;
- For all x: if A2(f(x),y) returns false for all y, then A1(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
<templatestyles src="Reflist/styles.css" />
- ↑ Elaine Rich, Automata, Computability and Complexity: Theory and Applications, Prentice Hall, 2008, Template:ISBN, section 28.10 "The problem classes FP and FNP", pp. 689–694
- ↑ M. Bellare and S. Goldwasser. The complexity of decision versus search. SIAM Journal on Computing, Vol. 23, No. 1, February 1994.
- ↑ Script error: No such module "citation/CS1".
Script error: No such module "Check for unknown parameters".
External links
Script error: No such module "Navbox".