Function problem - Revision history

~2025-31734-65 at 19:41, 9 December 2025

2025-12-09T19:41:25Z

← Previous revision		Revision as of 19:41, 9 December 2025
Line 1:		Line 1:
	{{short description\|Type of computational problem}}		{{short description\|Type of computational 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 output is not simply 'yes' or 'no'.		In [[computational complexity theory]], a '''function problem''' is a [[computational problem]] where a single output is expected for every input, but the output is more complex than that of a [[decision problem]]. For function problems, the output is not simply 'yes' or 'no'.

	== Definition ==		== Definition ==
	A ~~functional~~ problem <math>P</math> is defined by a [[Relation (mathematics)\|relation]] <math>R</math> over [[String (computer science)\|strings]] of an arbitrary [[Alphabet (computer science)\|alphabet]] <math>\Sigma</math>:		A ''function problem'' <math>P</math> is defined by a [[Relation (mathematics)\|relation]] <math>R</math> over [[String (computer science)\|strings]] of an arbitrary [[Alphabet (computer science)\|alphabet]] <math>\Sigma</math>:

	: <math>R \subseteq \Sigma^* \times \Sigma^*.</math>		: <math>R \subseteq \Sigma^* \times \Sigma^*.</math>

	~~An algorithm solves <math>P</math> if for every input <math>x</math> such~~ that ~~there exists a~~ <math>~~y</math> satisfying <math>(x, y) \in~~ R</math>~~, the algorithm produces one such <math>y</math>, and if there are no such <math>y</math>, it rejects~~.		Note that <math>R</math> does not have to be a [[Binary_relation#Types_of_binary_relations\|functional]] binary relation.

	A promise function problem ~~is allowed~~ to do anything (thus may not terminate) if no such <math>y</math> exists.		An [[algorithm]] solves <math>P</math> if for every input <math>x</math> such that there exists a <math>y</math> satisfying <math>(x, y) \in R</math>, the algorithm produces one such <math>y</math>, and if there are no such <math>y</math>, it rejects.

			A ''promise function problem'' permits the algorithm to do anything (thus may not terminate) if no such <math>y</math> exists.

	== Examples ==		== Examples ==
	A well-known function problem is given by the ~~Functional~~ Boolean ~~Satisfiability Problem~~, '''FSAT''' for short. The problem, which is closely related to the [[Boolean satisfiability problem\|'''SAT''']] decision problem, can be formulated as follows:		A well-known function problem is given by the functional Boolean satisfiability problem, '''FSAT''' for short. The problem, which is closely related to the [[Boolean satisfiability problem\|'''SAT''']] decision problem, can be formulated as follows:

	:Given a ~~boolean~~ formula <math>\varphi</math> with variables <math>x_1, \ldots, x_n</math>, find an assignment <math>x_i \rightarrow \{ \text{TRUE}, \text{FALSE} \}</math> such that <math>\varphi</math> evaluates to <math>\text{TRUE}</math> or decide that no such assignment exists.		:Given a [[propositional formula]] <math>\varphi</math> with variables <math>x_1, \ldots, x_n</math>, find an assignment <math>x_i \rightarrow \{ \text{TRUE}, \text{FALSE} \}</math> such that <math>\varphi</math> evaluates to <math>\text{TRUE}</math> or decide that no such assignment exists.

	In this case the relation <math>R</math> is given by ~~tuples~~ of suitably encoded ~~boolean~~ formulas and satisfying assignments.		In this case the relation <math>R</math> is given by pairs of suitably encoded propositional formulas and satisfying assignments.
	While a SAT algorithm, fed with a formula <math>\varphi</math>, only needs to return "unsatisfiable" or "satisfiable", an FSAT algorithm needs to return some satisfying assignment in the latter case.		While a SAT algorithm, fed with a formula <math>\varphi</math>, only needs to return "unsatisfiable" or "satisfiable", an FSAT algorithm needs to return some satisfying assignment in the latter case.

Line 22:		Line 24:

	== Relationship to other complexity classes ==		== 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]]'''.		Consider an arbitrary [[decision problem]] <math>L</math> in the class [[NP (complexity)\|'''NP''']]. By the definition of '''NP''', there is a system of certificates such that each problem instance <math>x</math> that is answered 'yes' has a [[polynomial]]-size certificate <math>y</math> that serves as a proof for the 'yes' answer (and problem instances answered 'no' have no such certificates). Thus, the set of these pairs <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 a ''function variant'' of <math>L</math>; it belongs to the class '''[[FNP (complexity)\|FNP]]'''.

			Conversely, every problem ''R'' in '''FNP''' induces a (unique) corresponding decision problem: given ''x'', decide if there exists some ''y'' such that ''R''(''x'',''y'') holds.

	'''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.		'''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 for which solutions can be found in polynomial time.

	== Self-reducibility ==		== Self-reducibility ==
	Observe that the problem '''FSAT''' introduced above can be solved using only polynomially many calls to a subroutine ~~which~~ decides the '''SAT''' problem: An algorithm can first ask whether the formula <math>\varphi</math> is satisfiable. After that the algorithm can fix variable <math>x_1</math> to TRUE and ask again. If the resulting formula is still satisfiable the algorithm keeps <math>x_1</math> fixed to TRUE and continues to fix <math>x_2</math>, otherwise it decides that <math>x_1</math> has to be FALSE and continues. Thus, '''FSAT''' is solvable in polynomial time using an [[Oracle machine\|oracle]] deciding '''SAT'''. In general, a problem in '''NP''' is called ''self-reducible'' if ~~its function variant~~ can be solved in polynomial time using an oracle ~~deciding the original~~ problem. Every '''[[NP-complete]]''' problem is self-reducible. It is conjectured {{By whom\|date=February 2020}} that the [[integer factorization problem]] is not self-reducible, because deciding whether an integer is prime is in '''P''' (easy),<ref name="AKS">{{cite journal \|first1=Manindra \|last1=Agrawal \|first2=Neeraj \|last2=Kayal \|first3=Nitin \|last3=Saxena \|url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf \|title=PRIMES is in P \|journal=[[Annals of Mathematics]] \|volume=160 \|year=2004 \|issue=2 \|pages=781–793 \|doi=10.4007/annals.2004.160.781 \|jstor=3597229 \|doi-access=free }}</ref> while the integer factorization problem is believed to be hard for a classical computer.		Observe that the problem '''FSAT''' introduced above can be solved using only polynomially many calls to a subroutine that decides the '''SAT''' problem: An algorithm can first ask whether the formula <math>\varphi</math> is satisfiable. After that the algorithm can fix variable <math>x_1</math> to TRUE and ask again. If the resulting formula is still satisfiable the algorithm keeps <math>x_1</math> fixed to TRUE and continues to fix <math>x_2</math>, otherwise it decides that <math>x_1</math> has to be FALSE and continues. Thus, '''FSAT''' is solvable in polynomial time using an [[Oracle machine\|oracle]] deciding '''SAT'''. In general, a problem in '''FNP''' is called ''self-reducible'' if it can be solved in polynomial time using an oracle for its induced decision problem. Every function variant of every '''[[NP-complete]]''' problem is self-reducible.
	There are several (slightly different) notions of self-reducibility.<ref>{{cite journal \|first= K.\|last= Ko\|title= On self-reducibility and weak P-selectivity\|journal= Journal of Computer and System Sciences\|volume= 26\|issue=2\|pages=209–221\|year=1983\|doi= 10.1016/0022-0000(83)90013-2}}</ref><ref>{{cite journal \|first= C.\|last=Schnorr\|title=Optimal algorithms for self-reducible problems\|journal=In S. Michaelson and R. Milner, Editors, Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming\|pages=322–337\|year=1976}}</ref><ref>{{cite journal \|first=A.\|last=Selman\|title=Natural self-reducible sets\|journal=SIAM Journal on Computing\|volume= 17\|issue=5\|pages=989–996\|year=1988\|doi=10.1137/0217062 }}</ref>		There are several (slightly different) notions of self-reducibility.<ref>{{cite journal \|first= K.\|last= Ko\|title= On self-reducibility and weak P-selectivity\|journal= [[Journal of Computer and System Sciences]]\|volume= 26\|issue=2\|pages=209–221\|year=1983\|doi= 10.1016/0022-0000(83)90013-2}}</ref><ref>{{cite journal \|first= C.\|last=Schnorr\|authorlink = Claus P. Schnorr\|title=Optimal algorithms for self-reducible problems\|journal=In S. Michaelson and R. Milner, Editors, Proceedings of the 3rd [[International Colloquium on Automata, Languages, and Programming]]\|pages=322–337\|year=1976}}</ref><ref>{{cite journal \|first=A.\|last=Selman\|title=Natural self-reducible sets\|journal=[[SIAM Journal on Computing]]\|volume= 17\|issue=5\|pages=989–996\|year=1988\|doi=10.1137/0217062 }}</ref>

	== Reductions and complete problems ==		== Reductions and complete problems ==
	Function problems can be [[Reduction (complexity)\|reduced]] much like decision problems: Given function problems <math>~~\Pi_R~~</math> and <math>~~\Pi_S~~</math> we say that <math>~~\Pi_R~~</math> reduces to <math>~~\Pi_S~~</math> if there ~~exists~~ polynomially-time computable functions <math>f</math> and <math>g</math> such that for all instances <math>x</math> of <math>R</math> and possible solutions <math>y</math> of <math>S</math>, it holds that		Function problems can be [[Reduction (complexity)\|reduced]] much like decision problems: Given function problems <math>R</math> and <math>S</math> we say that <math>R</math> reduces to <math>S</math> if there exist polynomially-time computable functions <math>f</math> and <math>g</math> such that for all instances <math>x</math> of <math>R</math> and possible solutions <math>y</math> of <math>S</math>, it holds that

	*If <math>x</math> has an <math>R</math>-solution, then <math>f(x)</math> has an <math>S</math>-solution.		*If <math>x</math> has an <math>R</math>-solution, then <math>f(x)</math> has an <math>S</math>-solution.
	*<math>(f(x), y) \in S \implies (x, g(x,y)) \in R.</math>		*<math>(f(x), y) \in S \implies (x, g(x,y)) \in R.</math>

	It is therefore possible to define '''FNP-~~complete'~~'' problems analogous to ~~the~~ NP-~~complete problem~~:		It is therefore possible to define ''FNP-hard'' problems analogous to NP-hard problems:

	A problem <math>~~\Pi_R~~</math> is '''FNP-~~complete~~''' if every problem in '''FNP''' can be reduced to <math>~~\Pi_R~~</math>. ~~The complexity class of~~ '''FNP-complete''' ~~problems~~ is ~~denoted by '''~~FNP-C''' ~~or '''FNPC~~'''. ~~Hence the~~ problem '''FSAT''' is ~~also~~ an '''~~FNP-complete~~''' ~~problem, and~~ it holds that <math>\mathbf{P} = \mathbf{NP}</math> if and only if <math>\mathbf{FP} = \mathbf{FNP}</math>.		A problem <math>R</math> is '''FNP-hard''' if every problem in '''FNP''' can be reduced to <math>R</math>. A problem <math>R</math> is '''FNP-complete''' if it is FNP-hard and in '''FNP'''. The problem '''FSAT''' is an FNP-complete problem, and hence by self-reducibility of '''FSAT''' it holds that <math>\mathbf{P} = \mathbf{NP}</math> if and only if <math>\mathbf{FP} = \mathbf{FNP}</math>.

	== Total function problems ==		== Total function problems ==
	The relation <math>R(x, y)</math> used to define function problems has the drawback of being incomplete: Not every input <math>x</math> has a counterpart <math>y</math> such that <math>(x, y) \in R</math>. Therefore the question of computability of ~~proofs~~ is not separated from the question of their existence. To overcome this problem it is convenient to consider the restriction of function problems to total relations yielding the class '''[[TFNP]]''' as a subclass of '''FNP'''. This class contains problems such as the computation of pure [[Nash equilibria]] in certain strategic games where a solution is guaranteed to exist. In addition, if '''TFNP''' contains any '''FNP-complete''' problem it follows that <math>\mathbf{NP} = \textbf{co-NP}</math>.		The relation <math>R(x, y)</math> used to define function problems has the drawback of being possibly incomplete: Not every input <math>x</math> necessarily has a counterpart <math>y</math> such that <math>(x, y) \in R</math>. Therefore the question of computability of outputs is not separated from the question of their existence. To overcome this problem it is convenient to consider the restriction of function problems to total relations yielding the class '''[[TFNP]]''' as a subclass of '''FNP'''. This class contains problems such as the computation of pure [[Nash equilibria]] in certain strategic games where a solution is guaranteed to exist. In addition, if '''TFNP''' contains any '''FNP-complete''' problem it follows that <math>\mathbf{NP} = \textbf{co-NP}</math>.

	==See also==		==See also==

imported>Nyngwang: /* Formal definition */ meta: rename section to "Definition".

2025-05-13T14:55:02Z

Formal definition: meta: rename section to "Definition".

New page

{{short description|Type of computational 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 output is not simply 'yes' or 'no'.

== Definition ==
A functional problem <math>P</math> is defined by a [[Relation (mathematics)|relation]] <math>R</math> over [[String (computer science)|strings]] of an arbitrary [[Alphabet (computer science)|alphabet]] <math>\Sigma</math>:

: <math>R \subseteq \Sigma^* \times \Sigma^*.</math>

An algorithm solves <math>P</math> if for every input <math>x</math> such that there exists a <math>y</math> satisfying <math>(x, y) \in R</math>, the algorithm produces one such <math>y</math>, and if there are no such <math>y</math>, it rejects.

A promise function problem is allowed to do anything (thus may not terminate) if no such <math>y</math> exists.

== Examples ==
A well-known function problem is given by the Functional Boolean Satisfiability Problem, '''FSAT''' for short. The problem, which is closely related to the [[Boolean satisfiability problem|'''SAT''']] decision problem, can be formulated as follows:

:Given a boolean formula <math>\varphi</math> with variables <math>x_1, \ldots, x_n</math>, find an assignment <math>x_i \rightarrow \{ \text{TRUE}, \text{FALSE} \}</math> such that <math>\varphi</math> evaluates to <math>\text{TRUE}</math> or decide that no such assignment exists.

In this case the relation <math>R</math> is given by tuples of suitably encoded boolean formulas and satisfying assignments.
While a SAT algorithm, fed with a formula <math>\varphi</math>, only needs to return "unsatisfiable" or "satisfiable", an FSAT algorithm needs to return some satisfying assignment in the latter case.

Other notable examples include the [[travelling salesman problem]], which asks for the route taken by the salesman, and the [[integer factorization problem]], which asks for the list of factors.

== 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.

== Self-reducibility ==
Observe that the problem '''FSAT''' introduced above can be solved using only polynomially many calls to a subroutine which decides the '''SAT''' problem: An algorithm can first ask whether the formula <math>\varphi</math> is satisfiable. After that the algorithm can fix variable <math>x_1</math> to TRUE and ask again. If the resulting formula is still satisfiable the algorithm keeps <math>x_1</math> fixed to TRUE and continues to fix <math>x_2</math>, otherwise it decides that <math>x_1</math> has to be FALSE and continues. Thus, '''FSAT''' is solvable in polynomial time using an [[Oracle machine|oracle]] deciding '''SAT'''. In general, a problem in '''NP''' is called ''self-reducible'' if its function variant can be solved in polynomial time using an oracle deciding the original problem. Every '''[[NP-complete]]''' problem is self-reducible. It is conjectured {{By whom|date=February 2020}} that the [[integer factorization problem]] is not self-reducible, because deciding whether an integer is prime is in '''P''' (easy),<ref name="AKS">{{cite journal |first1=Manindra |last1=Agrawal |first2=Neeraj |last2=Kayal |first3=Nitin |last3=Saxena |url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |title=PRIMES is in P |journal=[[Annals of Mathematics]] |volume=160 |year=2004 |issue=2 |pages=781–793 |doi=10.4007/annals.2004.160.781 |jstor=3597229 |doi-access=free }}</ref> while the integer factorization problem is believed to be hard for a classical computer.
There are several (slightly different) notions of self-reducibility.<ref>{{cite journal |first= K.|last= Ko|title= On self-reducibility and weak P-selectivity|journal= Journal of Computer and System Sciences|volume= 26|issue=2|pages=209–221|year=1983|doi= 10.1016/0022-0000(83)90013-2}}</ref><ref>{{cite journal |first= C.|last=Schnorr|title=Optimal algorithms for self-reducible problems|journal=In S. Michaelson and R. Milner, Editors, Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming|pages=322–337|year=1976}}</ref><ref>{{cite journal |first=A.|last=Selman|title=Natural self-reducible sets|journal=SIAM Journal on Computing|volume= 17|issue=5|pages=989–996|year=1988|doi=10.1137/0217062 }}</ref>

== Reductions and complete problems ==
Function problems can be [[Reduction (complexity)|reduced]] much like decision problems: Given function problems <math>\Pi_R</math> and <math>\Pi_S</math> we say that <math>\Pi_R</math> reduces to <math>\Pi_S</math> if there exists polynomially-time computable functions <math>f</math> and <math>g</math> such that for all instances <math>x</math> of <math>R</math> and possible solutions <math>y</math> of <math>S</math>, it holds that

*If <math>x</math> has an <math>R</math>-solution, then <math>f(x)</math> has an <math>S</math>-solution.
*<math>(f(x), y) \in S \implies (x, g(x,y)) \in R.</math>

It is therefore possible to define '''FNP-complete''' problems analogous to the NP-complete problem:

A problem <math>\Pi_R</math> is '''FNP-complete''' if every problem in '''FNP''' can be reduced to <math>\Pi_R</math>. The complexity class of '''FNP-complete''' problems is denoted by '''FNP-C''' or '''FNPC'''. Hence the problem '''FSAT''' is also an '''FNP-complete''' problem, and it holds that <math>\mathbf{P} = \mathbf{NP}</math> if and only if <math>\mathbf{FP} = \mathbf{FNP}</math>.

== Total function problems ==
The relation <math>R(x, y)</math> used to define function problems has the drawback of being incomplete: Not every input <math>x</math> has a counterpart <math>y</math> such that <math>(x, y) \in R</math>. Therefore the question of computability of proofs is not separated from the question of their existence. To overcome this problem it is convenient to consider the restriction of function problems to total relations yielding the class '''[[TFNP]]''' as a subclass of '''FNP'''. This class contains problems such as the computation of pure [[Nash equilibria]] in certain strategic games where a solution is guaranteed to exist. In addition, if '''TFNP''' contains any '''FNP-complete''' problem it follows that <math>\mathbf{NP} = \textbf{co-NP}</math>.

==See also==
*[[Decision problem]]
*[[Search problem]]
*[[Counting problem (complexity)]]
*[[Optimization problem]]

==References==
{{Reflist}}
{{more footnotes|date=October 2015}}
{{refbegin}}
* Raymond Greenlaw, H. James Hoover, ''Fundamentals of the theory of computation: principles and practice'', Morgan Kaufmann, 1998, {{ISBN|1-55860-474-X}}, p. 45-51
* [[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
{{refend}}

[[Category:Computational problems]]
[[Category:Functions and mappings]]