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, that is, it isn't just yes or no. == formal definition == a functional problem p is defined as a relation r(x,y) over a cartesian product over strings of an arbitrary alphabet \sigma: r \subset \sigma^* \times \sigma^* an algorithm a solves p if for every input x the algorithm either produces an output y such that (x, y) \in r or decides that no such y exists. == examples == a well-known function problem is given by the functional boolean satisfyability problem, fsat for short. the problem, which is closely related to the sat decision problem can be formulated as follows: given a boolean formula \varphi with variables x_1, \ldots, x_n, find an assignment x_i \rightarrow \{ \text{true}, \text{false} \} such that \varphi evaluates to \text{true} or decide that no such assignment exists. in this case the relation r(x, y) is given by tuples of suitably encoded boolean formulas and satisfying assignments. 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 in the class np. by definition each problem instance x which are answered 'yes' have a certificate y which servers as a proof for the 'yes' answer. thus, the set of these tuples (x, y) forms a relation. the complexity class derived from this transformation is denoted by \mathbf{f}(\mathbf{np}) or fnp for short. the mapping of the complexity class p is denoted by fp. the class fp is the set of function problems which can be solved by a deterministic turing machine in polynomial time, whereas fnp is the set of function problems which can be solved by a non-deterministic turing machine 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 \varphi is satisfiable. after that the algorithm can fix variable x_1 to true and ask again. if the resulting formula is still satisfiable the algorithm keeps x_1 fixed to true and continues to fix x_2, otherwise it decides that 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 np is called self-reducible if its funct
Computational_problems