From Wikipedia, the free encyclopedia

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

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 all function problems in which the solution is polynomially bounded, 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 (or Hamilton cycle if the salesman returning home is stipulated in the problem) with total weight less than or equal to K?

Given a solution to this problem, we can solve the travelling salesman problem as follows. Let Failed to parse (Missing texvc executable; please see math/README to configure.): n

by the number of edges and Failed to parse (Missing texvc executable; please see math/README to configure.): w_i
be the weight of edge Failed to parse (Missing texvc executable; please see math/README to configure.): i

. First rescale and perturb the weights of the edges by assigning to edge Failed to parse (Missing texvc executable; please see math/README to configure.): i

the new weight Failed to parse (Missing texvc executable; please see math/README to configure.): w'_i = 2^{(n+1)} w_i + 2^i

. This doesn't change the shortest Hamilton path, but makes sure that it is unique. Now add the weights of all edges to get a total weight Failed to parse (Missing texvc executable; please see math/README to configure.): M . Find the weight of the shortest Hamilton path by binary search: is there a Hamilton path with weight Failed to parse (Missing texvc executable; please see math/README to configure.): < M/2

is there a path with weight Failed to parse (Missing texvc executable; please see math/README to configure.): < M/4

etc. Then having found the weight Failed to parse (Missing texvc executable; please see math/README to configure.): W
of the shortest Hamilton path, determine which edges are in the path by asking for each edge Failed to parse (Missing texvc executable; please see math/README to configure.): i
whether there is a Hamiltonian path with weight Failed to parse (Missing texvc executable; please see math/README to configure.): W
for the graph modified so that edge Failed to parse (Missing texvc executable; please see math/README to configure.): i
has weight Failed to parse (Missing texvc executable; please see math/README to configure.): W+1
(if there is no such path in the modified graph, then edge Failed to parse (Missing texvc executable; please see math/README to configure.): i
must be in the shortest path for the original graph).  

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), and in fact it is complete for that class.ko:함수 문제 hr:Funkcijski problem ja:関数問題