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 A function problem P {\displaystyle P} is defined by a relation R {\displaystyle R} over strings of an arbitrary alphabet Σ {\displaystyle \Sigma } :
R ⊆ Σ ∗ × Σ ∗ . {\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}.}
Note that R {\displaystyle R} does not have to be a functional binary relation. An algorithm solves P {\displaystyle P} if for every input x {\displaystyle x} such that there exists a y {\displaystyle y} satisfying ( x , y ) ∈ R {\displaystyle (x,y)\in R} , the algorithm produces one such y {\displaystyle y} , and if there are no such y {\displaystyle y} , it rejects. A promise function problem permits the algorithm to do anything (thus may not terminate) if no such y {\displaystyle y} 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 SAT decision problem, can be formulated as follows:
Given a propositional formula φ {\displaystyle \varphi } with variables x 1 , … , x n {\displaystyle x_{1},\ldots ,x_{n}} , find an assignment x i → { TRUE , FALSE } {\displaystyle x_{i}\rightarrow \{{\text{TRUE}},{\text{FALSE}}\}} such that φ {\displaystyle \varphi } evaluates to TRUE {\displaystyle {\text{TRUE}}} or decide that no such assignment exists. In this case the relation R {\displaystyle R} is given by pairs of suitably encoded propositional formulas and satisfying assignments. While a SAT algorithm, fed with a formula φ {\displaystyle \varphi } , 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 L {\displaystyle L} in the class NP. By the definition of NP, there is a system of certificates such that each problem instance x {\displaystyle x} that is answered 'yes' has a polynomial-size certificate y {\displaystyle y} that serves as a proof for the 'yes' answer (and problem instances answered 'no' have no such certificates). Thus, the set of these pairs ( x , y ) {\displaystyle (x,y)} forms a relation, representing the function problem "given x {\displaystyle x} in L {\displaystyle L} , find a certificate y {\displaystyle y} for x {\displaystyle x} ". This function problem is called a function variant of L {\displaystyle L} ; it belongs to the class 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, 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 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 φ {\displaystyle \varphi } is satisfiable. After that the algorithm can fix variable x 1 {\displaystyle x_{1}} to TRUE and ask again. If the resulting formula is still satisfiable the algorithm keeps x 1 {\displaystyle x_{1}} fixed to TRUE and continues to fix x 2 {\displaystyle x_{2}} , otherwise it decides that x 1 {\displaystyle x_{1}} has to be FALSE and continues. Thus, FSAT is solvable in polynomial time using an 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.
… excerpt ends here. Continue reading the full article.
