Number two on the list is another big-dog in the world of maths. It’s so famous it’s even appeared in several Hollywood movies as directors try to add more credibility to their stories involving a robot-apocalypse – yes, I’m looking at you iRobot. The problem is called P versus NP.

It’s a relatively new addition to the world of maths in its current form, but the problem it’s trying to solve can be traced back to prehistoric times. Picture the scene: you wake up in your cave and you’re hungry, you’re thirsty and you could probably do with a wash as your attractive neighbour in the cave next door is coming over later for some quality ‘netflix and chill’ time. That’s a good point actually, you also need some flowers and the latest blockbuster cave painting. That makes five things, meaning five different places you need to visit. The question is: what’s the quickest route that you can take that visits all five locations and ends with you back at home. Today we just use Google, but as prehistoric you is not so lucky, let’s try some maths.

There are 5 places to visit, which means you have a choice out of 5 for the first place to go to. Once you’ve visited stop one, you then have a choice of 4 places to visit next. Then a choice of 3, then 2 and finally no choice for the last one as it’s the only one left. So in total that’s 5 x 4 x 3 x 2 x 1 = 120 different routes. We can probably cross a few routes off the list using our knowledge of the local area – maybe half of them pass through the swamplands home to Mr T. Rex, not only slowing you down severely, but also giving a high probability of death.

When you ask Google to work out the quickest route it will actually check all 120 possibilities and then give you the fastest. Not really a problem today, computers are quick and so you can probably get the quickest route in less than a second. But what if you want to visit 1000 different places – maybe you’re very popular in your prehistoric village and have many partners to visit – that means 1000 x 999 x 998 x … x 2 x 1 different routes to check. I’m not going to write down what that number is, but I can tell you that for a computer today to check that many different routes it would take longer than the age of the universe.

This is pretty much the P versus NP problem in a nutshell: if we can program a computer to recognise a solution to a problem quickly, can we also program it to find that solution quickly? With our example, your computer can tell you if your suggested route will visit all 1000 stops in a matter of milliseconds, but hell will quite literally freeze over before it can tell you if it’s the fastest of all possible routes. P versus NP is asking whether or not there is a shortcut that doesn’t involve checking every single possible combination.

Most mathematicians believe that P does not equal NP and in fact if the two are shown to be equal the world as we know it will probably end. P=NP means we can instantly break any code that has ever existed, predict stock market trends before they happen and most worryingly build robots with artificial intelligence higher than anyone on earth. Better get Will Smith on speed dial just in case iRobot wasn’t too far wrong after all…

 

You can listen to Scott Aaronson being interviewed about the problem here.

I’ve written a series of articles on each of the 7 Millennium Problems which can be found here.