Function problem
Encyclopedia
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. 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 class
es 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 solution to this problem, we can solve the travelling salesman problem as follows. Let
be the number of edges and 
be the weight of edge 
. First rescale and perturb the weights of the edges by assigning to edge 
the new weight 
. 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 
. Find the weight of the shortest Hamilton path by binary search: is there a Hamilton path with weight 
; is there a path with weight 
etc. Then having found the weight 
of the shortest Hamilton path, determine which edges are in the path by asking for each edge 
whether there is a Hamiltonian path with weight 
for the graph modified so that edge 
has weight 
(if there is no such path in the modified graph, then edge 
must be in the shortest path for the original graph).
This places the travelling salesman problem in the complexity class FPNP (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.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, a function problem is a computational problem
Computational problem
In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve. For example, the problem of factoring...
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
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
, that is, it isn't just YES or NO. Notable examples include the travelling salesman problem
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
, 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 class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
es in the same way as decision problems. For example FP
FP (complexity)
In computational complexity theory, the complexity class FP is the set of function problems which can be solved by a deterministic Turing machine in polynomial time; it is the function problem version of the decision problem class P...
is the set of function problems which can be solved by a deterministic Turing machine in polynomial time, and FNP
FNP (complexity)
In computational complexity theory, the complexity class FNP is the function problem extension of the decision problem class NP. The name is somewhat of a misnomer, since technically it is a class of binary relations, not functions, as the following formal definition explains:This definition does...
is the set of function problems which can be solved by a non-deterministic Turing machine
Non-deterministic Turing machine
In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers....
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 graphDirected graphA directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
and an integer K, is there a Hamilton path (or Hamilton cycle if the salesman must return home) 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
be the number of edges and be the weight of edge . First rescale and perturb the weights of the edges by assigning to edge the new weight . 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 . Find the weight of the shortest Hamilton path by binary search: is there a Hamilton path with weight ; is there a path with weight etc. Then having found the weight of the shortest Hamilton path, determine which edges are in the path by asking for each edge whether there is a Hamiltonian path with weight for the graph modified so that edge has weight (if there is no such path in the modified graph, then edge must be in the shortest path for the original graph).This places the travelling salesman problem in the complexity class FPNP (the class of function problems which can be solved in polynomial time on a deterministic Turing machine with an oracle
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
for a problem in NP), and in fact it is complete
Complete (complexity)
In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class...
for that class.
See also
- Decision problemDecision problemIn computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
- Search problemSearch problemIn computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation...
- Counting problem (complexity)
- Optimization problemOptimization problemIn mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...