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 output is not simply 'yes' or 'no'. Formal definition. A functional problem formula_1 is defined as a relation formula_2 over strings of an arbitrary alphabet formula_3: An algorithm solves formula_1 if for every input formula_6 such that there exists a formula_7 satisfying formula_8, the algorithm produces one such formula_7. 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: In this case the relation formula_2 is given by tuples of suitably encoded boolean formulas and satisfying assignments. While a SAT algorithm, fed with a formula formula_10, 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 formula_17 in the class NP. By the definition of NP, each problem instance formula_6 that is answered 'yes' has a polynomial-size certificate formula_7 which serves as a proof for the 'yes' answer. Thus, the set of these tuples formula_20 forms a relation, representing the function problem "given formula_6 in formula_17, find a certificate formula_7 for formula_6". This function problem is called the "function variant" of formula_17; it belongs to the class 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, 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 formula_10 is satisfiable. After that the algorithm can fix variable formula_27 to TRUE and ask again . If the resulting formula is still satisfiable the algorithm keeps formula_27 fixed to TRUE and continues to fix formula_29, otherwise it decides that formula_27 has to be FALSE and continues. Thus, FSAT is solvable in polynomial time using an 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 that the integer factorization problem is not self-reducible. Reductions and complete problems. Function problems can be reduced much like decision  problems: Given function problems formula_31 and formula_32 we say that formula_31 reduces to formula_32 if there exists polynomially-time computable functions formula_35 and formula_36 such that for all instances formula_6 of formula_2 and possible solutions formula_7 of formula_40, it holds that It is therefore possible to define FNP-complete problems analogous to the NP-complete problem: A problem formula_31 is FNP-complete if every problem in FNP can be reduced to formula_31. 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  formula_48 if and only if formula_49. Total function problems. The relation formula_50 used to define function problems has the drawback of being incomplete: Not every input formula_6 has a counterpart formula_7 such that formula_8. 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 formula_54.