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. Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ...

Notable examples include the traveling salesman problem which asks for the route taken by the salesman, and the integer factorization problem, which asks for the list of factors. The traveling salesman problem or travelling salesman problem (TSP), also known as the traveling salesperson problem, is a problem in discrete or combinatorial optimization. ... In mathematics, the integer prime-factorization (also known as prime decomposition) problem is this: given a positive integer, write it as a product of prime numbers. ...

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. In computational complexity theory, a complexity class is a set of problems of related 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. ... The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ... In computational complexity theory, Polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ... In computational complexity theory, the complexity class FNP is the set of function problems which can be solved by a non-deterministic Turing machine in polynomial time. ... In theoretical computer science, an ordinary (deterministic) Turing machine (DTM) has a transition rule that specifies for a given current state of the head and computer (s,q) a single instruction (s, q, d), where s is the symbol to be written by the head, q is the subsequent state... In computational complexity theory, Polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ...

For all 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 traveling salesman problem is this: In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. ...

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 traveling salesman problem as follows. Let n by the number of edges and w_i be the weight of edge i. First rescale and perturb the weights of the edges by assigning to edge i the new weight w'_i = n²w_i + 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 M. Find the weight of the shortest Hamilton path by binary search: is there a Hamilton path with weight < M / 2; is there a path with weight < M / 4 etc. Then having found the weight W of the shortest Hamilton path, determine which edges are in the path by asking for each edge i whether there is a Hamiltonian path with weight W for the graph modified so that edge i has weight W + 1 (if there is no such path in the modified graph, then edge i must be in the shortest path for the original graph). This article just presents the basic definitions. ... In the mathematical field of graph theory, a Hamiltonian path is a path in a undirected graph which visits each vertex exactly once. ... In computer science, binary search is a search algorithm for searching a set of sorted data for a particular value. ...

This places the traveling 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. In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. ...