The Travelling Salesman Problem (TSP) is one of the most famous unsolved problems in mathematics and computer science. First posed in 1930, the problem can be phrased like this:
“Given a set of cities and distances between each pair of cities, what is the shortest route that visits every city exactly once, and returns to the origin city?”
At first glance, this problem might seem quite straightforward. The number of cities we have is finite, so brute-forcing every possible route will allow us to compare each one and thus determine the shortest one. Simple, right?
To show why this approach, although correct, is impractical, let’s consider a version posed by Procter & Gamble, containing 33 cities across America. The company offered successful contestants a cash prize of $10,000, equivalent to over $100,000 in today’s money.
Let’s label the 33 cities ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567. Assume we start at city A. For our second city to visit, we have 32 choices. Following this, we have 31 choices for which city to visit third. In this manner, it is easy to see that we have 32 x 31 x 30 x … x 2 x 1 = 32! routes. This is over 1035.
If when the universe began we had tasked the Frontier OLCF-5, currently the world’s fastest supercomputer, to check every single route, it would still be running. Considering it has over 8.5 million cores and can carry out one quintillion (1018) arithmetic operations per second, perhaps we should consider a different perspective.

Framing the problem in terms of computational complexity, the problem can be rephrased:
“Given a set of cities and distances between each pair of cities, does there exist a polynomial-time algorithm capable of determining the shortest route that visits every city exactly once, and returns to the origin city?”
A polynomial-time algorithm refers to an algorithm that has the property that, as the size n of the problem grows, the time taken to solve it grows proportionally to some polynomial of degree k. Put simply, if we consider a TSP with n cities, a polynomial-time algorithm should take at most nk ‘steps’ to solve the problem, for some constant k. We call the time complexity of such an algorithm O(nk) (read “big O of n to the k”, where ‘O’ stands for “Order”), with the brute-force approach we tried above having a time complexity of O(n!).

It might seem counterintuitive that the value of k is not important; k could be 1000 and the algorithm would still be considered efficient. But polynomial time is significant because it implies that as the problem size increases, the time taken to solve it grows at a manageable rate - unlike exponential or factorial time, which quickly becomes unfeasible for even the fastest computers. This distinction between ‘good’ and ‘bad’ algorithms gave mathematicians a concrete target to aim towards.
Many algorithms and heuristics have been created to come up with optimal or near-optimal solutions to the TSP. Systems used to solve large-scale TSP problems, such as Concorde, employ many of these techniques. Concorde has previously solved an 85,900 city TSP, and can find near-optimal solutions for TSPs with millions of cities. Currently, the best algorithm for exact solutions (Held-Karp algorithm) to the TSP has time complexity O(n^2∙2^n). Although polynomial-time algorithms for approximate solutions (which can guarantee a tour with a small level of error to the optimal tour) exist, one that can produce optimal tours has not yet been developed, nor do we know if one even exists. In the rest of this article, I will not describe the algorithms and heuristics developed for this problem, rather, I would like to discuss the complexity of this problem, and how it can be generalised to explain some key concepts in theoretical computer science.
For this section, we will again have to change the definition of the problem to a decision problem i.e. one with a yes/no answer.
“Given a set of cities and distances between each pair of cities, does there exist a route that visits every city exactly once, and returns to the origin city, of length at most k?”
The reason for this alteration is that if you think the answer is yes, you can prove it by presenting the route itself. Anyone who is sceptical of your answer can add up the distances and see that the route you presented has distance ≤ k. In other words, a polynomial-time algorithm exists to verify if the statement is true (but not necessarily if it’s false). This puts it in a class of decision problems called NP.
Although you can verify a “yes” answer to this problem using a polynomial-time algorithm, we don’t yet know if you can solve it as easily. Decision problems which can be solved in polynomial-time belong to a class called P. If someone found a polynomial-time algorithm to solve it, the TSP would belong to the class P; similarly, proving that one does not exist would prove that it does not belong to the class P.
It can be proved that some problems in NP, including the decision version of the TSP, have the property that every other problem in NP can be reduced to it. After some abstraction, every problem in NP is equivalent to and boils down to solving these special problems. We call these problems NP-complete.
Here's where it gets interesting. The existence of these NP-complete problems has two implications:
Proving that any one NP-complete problem can be solved in polynomial-time proves that all problems in NP can be solved in polynomial-time
Proving that any one NP-complete problem cannot be solved in polynomial-time proves that no problems in NP can be solved in polynomial-time
These essentially equivalent claims arise due to the reduction property mentioned earlier. If one NP-complete problem X can be solved in polynomial-time, we can reduce all other problems in NP to X, and hence solve all problems in NP in polynomial-time.
On the other hand, if we can prove that one NP-complete problem Y cannot be solved in polynomial-time, we can reduce all problems in NP to Y, and hence not be able to solve any problems in NP in polynomial-time.
What you might have spotted is that these claims are essentially saying that if we prove that an NP-complete problem has a polynomial-time solution, then all problems in NP are in P, and thus P=NP. However, if we prove that an NP-complete problem does not have a polynomial-time solution, then P≠NP. This is known as the P vs NP problem that you may have heard of.
First proposed in 1971, P vs NP remains arguably the most famous unsolved problem in computer science. The general consensus along academics is that P≠NP. If they are equal, there will be significant consequences. One of the most notable is that all of our data will be in danger of theft. Modern encryption systems utilise cryptosystems such as RSA encryption, which rely on the fact that no polynomial-time algorithm for integer factorisation of very large numbers is known. Since the problem of integer factorisation of numbers is in NP (given the factorisation itself, it is easy to verify that the factorisation is correct), showing that P=NP would mean that there exist ways to break encryption systems, and hence steal data.
P vs NP is one of the 7 Millennium Prize Problems presented by the Clay Mathematical Institute, offering a $1 million prize for complete solutions to any of them. Only one of them, the Poincaré conjecture, has been solved to date. Grigori Perelman, who solved the problem and rejected the monetary prize, said:
"If the proof is correct, then no other recognition is needed."