Function problem

In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO.

Notable examples include travelling salesman problem which asks for the route taken by the salesman, and the integer factorization problem, which asks for a list of factors.

Function problems are more awkward to study than decision problems because they don't have an obvious analogue in terms of languages, and because the notion of reduction between problems is more subtle as you have to transform the output as well as the input.

Function problems can be sorted into complexity classes in the same way as decision problems, for example FP is the set of function problems which can be solved by a deterministic Turing machine in polynomial time, and FNP is the set of function problems which can be solved by a non-deterministic Turing machine in polynomial time.

For most function problems there is an analogous decision problem such that the function problem can be solved by polynomial time Turing reduction to that decision problem. For example, the decision problem analogue to the travelling salesman problem is this:

Given a weighted directed graph and an integer K, is there a Hamilton path with total weight less than or equal to K?

Given a solution to this problem, we can solve the travelling salesman problem as follows: add the weights of all edges to get a maximum weight M; then find the minimum weight of any Hamilton path by binary chop (is there a path with weight ≤ M/2? is there a path with weight ≤ M/4? etc); then having found the minimum weight W, determine which edges are in the path by asking for edge E whether there is a Hamilton path with weight W for the graph modified so that edge E has weight W+1 (if there is, then edge E is not in that path).

This places the travelling salesman problem in the complexity class FP^NP (the class of function problems which can be solved in polynomial time on a deterministic Turing machine with an oracle for a problem in NP).