The granddaddy of all optimisation problems is known as The Travelling Salesman Problem (TSP). An optimisation problem is simply one in which the task is to find the best possible solution from all the other, worse, ones. TSP dates back to the 19th century when it was first written down in 1832. What at first seemed to be a simple problem, up to the present day, the ‘route finding’ problem has consumed amounts of time money and energy. It is formulated as follows:
‘Given a list of cities and the distance between each pair of cities, search a weighted, complete graph to find the optimal (shortest) cycle that visits every node exactly once – except for the start node, which is also the end node.’
In other words, the input to the TSP is a weighted, complete graph and the output is a sequence of nodes that represents the shortest cycle that includes every node from the graph exactly once (except for the first and last node).
This doesn’t sound very difficult to solve, but as the number of cities grow, the number of possible routes grows even fast at the factorial rate. The factorial of a number is the result obtained by multiplying all the whole numbers between 1 and that number. So, 3 factorial (written as 3!) is 1 x 2 x3 = 6. In the TSP, the number of possible routes can be calculated for n greater than 2, using the formula
number of routes = (n – 1)! / 2.
The TSP is not itself a real-world problem, but many extremely important real-world problems – in planning, logistics and electronic engineering – have an identical structure. Computers work constantly on variations of the TSP as part of our everyday life: routing parcels to their destinations, keeping track of railway rolling stock and ensuring the efficient use of cars and aircraft to reduce fuel consumption. The TSP even has roles to play in matching DNA traces retrieved at crime series to DNA samples of suspects, and comparing the genetic similarities between species in studies of evolution.
The TSP is an example of a problem that may lie on either side of the divide between tractable and intractable problems. Although many people have tried to solve the TSP, no one has been able to come up with a tractable algorithm and neither has no one been able to prove that the lower bound of this problem lies outside the class P (polynomial problems). So, the complexity of the TSP is unknown. With dynamic programming the best we can reach is O(n2 * 2n) better than O(n!) but not subexponential.
The decision TSP is defined as follows. Given a weighted complete graph, decide whether there is a cycle that visits every node exactly once, except that the starting and end point are the same node, and whose total weight is at most k. It belongs to a class of problems that is known as the class NP. A decision problem dp is in NP if there is a tractable algorithm V, a verifier, such that for any possible input x: dp(x) = 1 if an only if there is a polynomial-size certificate w such that V returns 1 for (x, w). In other words, a decision problem is in NP if, for the inputs where the answer is 1 (‘yes’), there exists a certificate (verifying the correctness of the answer) that can be efficiently checked. If there is a route of at most length k (i.e. the answer is ‘yes’) for a given complete weighted graph, then there is a polynomial-size certificate (the route itself) to back up this answer. The verifier algorithm can check in polynomial time that each node, except for the start/end node occurs only once, and that the sum of the distances between the nodes on the tour is less than k.
NP is characterised only for decision problems.