The following is an extract from our Lost in Space-Time newsletter. Each month, we hand over the keyboard to a physicist or mathematician to tell you about fascinating ideas from their corner of the universe. You can sign up for Lost in Space-Time here.
How far would you be willing to go for $1 million? Well, what if I told you that you can earn that prize by simply solving any one of the six remaining Millennium Prize Problems? The caveat being they are considered to be the most challenging unsolved problems currently facing mathematicians. Announced in the year 2000 – hence the name Millennium Problems – they were selected by an advisory committee, with the criteria for selection being “a classical problem which has resisted solution for many years”. Notice that there’s no mention of “helping society”, or “furthering our understanding of the universe”. Instead, the seven original problems were simply the hardest questions that any mathematician has come up with, ever.
The list of candidates includes the Riemann hypothesis, P versus NP, the Navier-Stokes equations, the Hodge conjecture, the Birch and Swinnerton-Dyer conjecture, the Yang-Mills mass gap hypothesis and the Poincaré conjecture. That last one was solved in 2003 by Russian mathematician Gregori Perelman – a whole other story I unfortunately don’t have space-time for. You may recognise a few of the particularly notorious ones (I’m looking at you, Riemann), but you may also be surprised by some of the omissions, such as the Collatz conjecture. And then there’s the case of Fermat’s last theorem, which had remained unproven for more than 350 years. It would undoubtedly have been included – if it hadn’t been solved just a few years earlier by Andrew Wiles.
Advertisement
But one of my favourite problems to talk about – because, in my opinion, it’s the easiest to get your head around – is P versus NP.
The question of P versus NP comes from the field of computational complexity, which basically looks at how computers solve problems. It asks whether two classes of problem – P and NP – are actually the same thing, despite seemingly having different definitions. To break this one down, let’s start with those definitions.
A P problem is one that is “easy” for a computer to solve. This comes down to the time it takes for a computer to solve the problem. Take the example of simultaneous equations. If we have a pair of equations, say:
ax + by = c
dx + ey = f
and we want to solve for x and y, given the values of the constants a, b, c, d, e and f, then a computer can just use the formula:
x = (ed – bf)/(ad – bc)
y = (af – ce)/(ad – bc)
It substitutes the values of the constants and then calculates the multiplications, divisions, additions and subtractions to get the solution. On a modern computer this is all done in a fraction of a second. Now, if we increase the number of equations, so instead of two equations in two unknowns, we have seven equations in seven unknowns, or 42 equations in 42 unknowns, the computer can still solve the problem using the same approach. There are a few more steps, but thinking of the 42 equations as 21 pairs, the amount of time taken is just 21 times the time it took to solve the original two equations. So what we are seeing is that, as we increase the number of equations, the time taken to solve them increases at the same rate. This is called a linear relationship. Double the number of equations, double the time taken for a solution.
Now let’s look at something a little trickier, called the travelling salesman problem. Imagine you are selling a product (the examples in textbooks always seem to be fridge magnets for some reason). You want to travel to several cities to reach your customer base, but as business is currently a little slow, you only have enough money to cover 200 miles. So really, what you want to know is whether it is possible to find a route between the six cities on your itinerary with a total trip length of 200 miles.
There are several ways to approach this problem. Some kind of sensible trial-and-error (so, not zigzagging between cities at opposite ends of the country) is a good way to start investigating potential routes. But in order to be certain one doesn’t exist, you would actually need to try them all. So how many are there?
If there are six cities, you have a choice of six starting locations. This is a fictional problem where we can choose the most convenient start point – let’s say the company will pay for your flight, but not your petrol. Once you’ve picked where to start, you have five choices of where to go next. Then you have four choices of which city comes third, then three choices, then two and finally only one city left to visit, so you have to go there to end. That’s 6 x 5 x 4 x 3 x 2 x 1 = 720 different routes to visit all six cities. If you measure the distance of each of these routes, you can look through the list. If any of them have a total distance of 200 miles or less, you’ve done it – you’ve found a possible solution.
And of course, if all 720 routes have a total distance greater than 200, then you can conclude it’s impossible and you’ll need to get back on the phone with your boss for a reassignment (or an increased petrol budget).
While this might seem like a contrived example, problems of this nature occur much more frequently than you might think in the real world. To optimise transportation routes, increase the efficiency of logistical or manufacturing operations or even improve our understanding of DNA sequencing, you will have to solve a version of the travelling salesman problem.
Now, when we were talking about P problems earlier, we saw in the example of solving simultaneous equations that doubling the number of equations led to double the time it takes for a computer to solve the problem. So, let’s try something similar with the travelling salesman. Suppose we now want to visit 12 cities, and we’ve managed to secure an increase to our petrol budget to cover 500 miles. Is there a route between all 12 cities with a total distance less than 500?
We proceed exactly as before and consider all possible solutions. Again, we could try a few obvious routes to start, but if none of those are successful, then we’re going to need a systematic way to check every possible route if we want to be certain a solution does – or doesn’t – exist.
We now have 12 choices for where to start (good to see the flight budget remains intact), 11 choices of where to go next, and so on, for a total of 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 479,001,600.
That is a LOT of potential routes – almost half a billion of them. And more importantly, it’s significantly more than double the number of routes we had to check for six cities (720). So, what’s going on here?
Some of you may recognise the function that appeared when we were calculating the number of routes – the factorial function: n! = n x (n-1) x (n-2) x … x 2 x 1. The exclamation mark means you take the current whole number and multiply it by all whole numbers smaller than it exactly once, until you reach 1.
These numbers are big. Like, really big. And they are definitely no longer linear. In fact, factorials grow so quickly that they are even faster than exponential growth, often seen as the standard-bearer for “growing quickly”.
The reason exponential growth is used as a baseline, particularly when looking at computational complexity, is we classify any problem with a computational time that is exponential or greater as “hard”. Since the time taken to find the solution of the travelling salesman problem grows faster than exponential time, it is therefore hard. So it is definitely not a P problem, which is easy to solve.
But it is an NP problem. An NP problem is one where it is “easy” – meaning it can be computed in less than exponential time – to check the answer. Given a problem, and given a possible solution, it is easy for a computer to determine whether or not that solution is correct.
Let’s apply this idea to the travelling salesman problem. If I give you what I think is a correct solution, i.e. a route passing through all 12 cities with a total length less than 500 miles, you can check it pretty quickly. Does it have all 12 cities? Is the total length less than 500 miles? If the answer to both questions is yes, then the solution is valid. Otherwise, it’s invalid. It’s very quick for a computer to check the answer, so the travelling salesman is an NP problem. It’s still hard to solve – but checking a given answer is easy.
Now we have both definitions, so let’s go back to the name of the problem: P versus NP. The “versus” suggests we want to consider how the two problem sets are related. A P problem is one that is easy to solve, and a NP problem is one that is easy to check, so how do they interact? Think about the following situation: I have a problem that is easy to solve, and I want to check whether a solution I’ve been given is correct. Now, I could try and come up with a method to verify the solution, not too dissimilar from what we used for the travelling salesman problem above. But since it’s really quick to solve the problem in the first place, let’s just do that and then compare the solution we obtain with the one we’ve been given to check.
This is exactly how it’s done. If a problem is easy to solve – a P problem – then it is always going to be easy to check – an NP problem – because we can just solve it! So any problem that is in P, is by definition always going to be in NP, meaning we can say P is contained within NP.
Finally, we come to the million-dollar question – does it work the other way around? In other words, if a problem is easy to check, NP, does that mean it is also easy to solve, P?
If you’ve followed so far, you are hopefully screaming at your screen, “Of course not! We’ve just looked at the travelling salesman problem, which is easy to check (NP), but not easy to solve (P)! We have something that is in NP, but not in P, so the two problem sets cannot possibly be equal!”
And you’re right… to an extent. Using our current best approach of trying all possible routes, the travelling salesman problem is indeed hard to solve. But how do we know there isn’t another better, much faster, solution? Just because we can’t think of one right now doesn’t mean it doesn’t exist… We would need to prove no matter what method we use, it will always take at least exponential time to solve the travelling salesman problem in order to conclude without any doubt that it lies in NP, but not P. This is the power – and difficulty – of mathematical proof.
The P versus NP problem was first mentioned by computer scientist Stephen Cook in 1971, and over the past 53 years, we haven’t been able to come up with a method of solving the travelling salesman problem in less than exponential time. It certainly looks a very likely candidate for something that is NP and not P, thus showing they are unequal. But until we have proof all other methods would be equally slow or we discover a novel method of solving it in less than exponential time, the million-dollar prize will remain unclaimed.
And that’s all there is to it. Just come up with a proof everything in NP is also in P, or a counterexample of something that is NP but can never be P, and you’ve earned yourself a cool $1 million. Although a word of warning: if you divide the million dollars by the estimated amount of time Perelman spent on his successful proof of the Poincaré conjecture, it comes out to around minimum wage.
