An introduction to the traveling salesman problem

There's always a relevant XKCD comic. From https://xkcd.com/399/

What's the most efficient way of going through a set of cities once and coming back to where you started? As simple as it sounds, iterating through every possible combination would be next to impossible if the list of cities is big enough. If there's 100 cities and you pick one as the starting point, there's still 99 more cities to choose from. The number of combinations would be 100(100-1)(100-2)... until there's only one choice left. The amount of possible solutions increases at a staggering rate as the amount of cities increase. Researchers have worked on trying to find a way to solve it as fast as possible. To understand the traveling salesman problem (TSP) in terms of computer science, we must first understand the concepts of time complexity.

Given an input n, the time complexity is determined by how much of the given input, n, we have to go through. For example, if I were to look through 100 boxes one by one, the worst case scenario would be finding what I was looking for after going through all 100 boxes. The time complexity of the example would be written as O(n) in the Big O notation because given the input, n = 100, and my search method, I need to look through all of them. Although I can find whatever it is in the first box I look into, time complexity is usually determined by the worst case scenario.

These time complexities are grouped into classes and the two important classes regarding TSP are classes P and NP. Problems in class P are solvable in polynomial time with a deterministic algorithm where one input can only have one output. Polynomial time meaning time complexities such as n, nlog(n), n¹⁰, etc. Problems in class NP, non-deterministic polynomial time, cannot be solved in polynomial time with a deterministic algorithm, but solutions can be checked in polynomial time. TSP falls under the class NP because while solving it is difficult we can verify the solution by checking if the solution goes through every city just once which takes a polynomial amount of time. The goal now is to find the algorithm that can solve TSP within polynomial time.

Why is this important? TSP is just one small droplet in the overarching problem of P versus NP. If a solution can be found for the decision version of TSP, this would prove P = NP meaning all NP-complete problems can be solved within a minimal amount of time. NP-complete problems are problems with no known shortcuts. This breakthrough will change the works of medical sciences, mathematics, engineering, transportation, and computer science. A lot of fundamental problems are NP-complete such as searching through DNA sequences, optimal protein folding, and shortening mathematical proofs. But even after decades of research, P = NP still hasn't been proven and it's becoming more of a fantasy. For more information on P and NP problems or an overview on P versus NP in general, Lance Fortnow wrote a great article called "The status of the P versus NP problem" in the Communications of the ACM magazine. He also has a much better blog on dealing with computational complexity at http://blog.computationalcomplexity.org/.

References

Lecture by Erik Demaine on Computational Complexity

Fortnow, L. (2009). The status of the P versus NP problem. Association for Computing Machinery.Communications of the ACM, 52(9), 78. doi:http://dx.doi.org/10.1145/1562164.1562186

Hamburger, H. & Richards, D. (2002). Logic and language models for computer science. Upper Saddle River, N.J: Prentice Hall.