What's the fastest way to the shoe shop?

The P vs NP problem is a puzzle that has been around since the dawn of civilisation -if you have to pop the shoe shop, the bank and the grocers, which route is the quickest? Nowadays, you'd Google it, but is the route we are given actually the quickest? To find the shortest route, or optimal solution, maths says that we would have to consider every possible route to be sure that we have found the fastest. This may not seem too hard if we are visiting only 3 or 4 places, but if we were visiting say 1000, it would take computers more than 13 billion years to consider every solution. Scott Aaronson, from MIT, spoke to Kat Arney about the problem...

Scott - In one sentence, the question asks, if you can programme your computer to quickly recognise the solution to a problem then can you also quickly programme your computer to quickly find a solution? Okay, so you use the example of the traveling salesman or sales person problem where you're given a bunch of places you want to visit and the distance between every pair of them, and you want to know whether there's a route that will visit each place let's say, within at most, 2 hours total travel time. Now, the key aspects of this problem are first of all, that there is a finite but astronomically large set of possible solutions. So in principle, you could just check all the solutions one by one but in reality as you said, like a thousand places to visit, there's the number of possibilities is like a 1,000 times 999, times 998 and so forth. It is way more than the number of atoms in the visible universe. Even with their fastest supercomputers today, you just couldn't try all of them. And the question is, are there checkable problems that require an exponential amount of time to actually find the solution? So, that would be P not equal to NP or all the NP problems actually also in P, or are they all solvable by some clever shortcut where you could do it using only a polynomial or a reasonable amount of time?

Kat - So, one way I've heard this described, this is basically like asking a riddle. If you hear the answer, you go, "Yeah, that's definitely the right answer. I can tell you that" whereas you might have to puzzle through a whole load of different answers. What would be the benefits of being able to figure this out because it seems like quite an interesting puzzle, but what could be the benefits of it?

Scott - Well, the implications are immense actually. This problem has, I think the most direct practical implications of any of these Clay problems. So first of all, it would mean that all of the cryptography that we currently use on the internet could be broken. The Riemann Hypothesis as Dr. du Sautoy was saying is, sort of indirectly connected to cryptography. If P were equal to NP, that would directly imply that all of the cryptography that we use to protect our credit card numbers could be broken because all of it is based on NP problems if you like.

Kat - So, this would basically say, "Yep! All of these can be solved. We can figure this one out"?

Scott - That's exactly right. That doesn't mean that if P is not equal to NP that all of our cryptography is secure. But P not equal to NP is sort of the least that you need to have secure cryptography on the internet. In addition to that, P equals NP would be a huge boone for artificial intelligence. If you have let's say a neural network, you could just sort of very, very quickly find the best setting that causes the neural net to do the best at recognising faces or whatever it's supposed to do. And then here's something to ponder, if P equals NP, that would also help in solving math problems like the Clay problems themselves. I like to argue that P versus NP is actually the most important of all these problems. The argument is simply, if you prove that P equals NP, that would not only solve this one problem. It would mean that you could programme your computer to solve all the others for you.

Kat - Where do you think the solution for this problem might come from? Are there any hints, any teasers so far?

Scott - There are hints. I think we know a lot more about this problem than we do when it was first formulated around the middle of the 20th century. We know a lot about what doesn't work. I could say that almost all of us in this field conjecture that P is not equal to NP.