Get cash from the cash point, go to the supermarket, pick up kids from school and prescription from doctor. In what order should you do these things so that the distance you've got to drive is as short as possible? Not a particularly exciting problem, you might think, but it's one that fascinates mathematicians. That's because in general it's very hard to solve and opens the door on one of the trickiest unanswered questions in mathematics.
The problem is called the travelling salesman problem and the general form goes like this: you've got a number of places to visit, you're given the distances between them, and you have to work out the shortest route that visits every place exactly once and returns to where you started. If it's a small number of places, you can find the answer quite easily simply by looking at all the possible routes. As the number of places grows, this becomes incredibly tedious. Is there a better method for doing this, an algorithm, that can give you an answer in a reasonable amount of time even if the number of places is huge?
Of course the answer depends on what you mean by reasonable. The time it takes an algorithm to conclude its task is proportional to the number of steps it has to execute. Perhaps you can find an algorithm that takes $n^2$ steps to solve the problem for $n$ places. That would mean 100 steps if the problem involves visiting ten places and 400 steps if it involves 20 places. That may seem bad but imagine the algorithm takes $2^n$ steps to solve the problem for $n$ places. Then ten places would require 1,024 steps and 20 places more than a million. This is rapidly exploding exponential growth.![Graphs](http://plus.maths.org/content/sites/plus.maths.org/files/articles/2012/salesman/graphs.png)
The functions 2n (black), n3 (red) and n2 plotted against n. You can see that 2n grows fastest for larger n.
This leads us to the big question: are there any polynomial-time algorithms for problems in the NP class that simply haven't been discovered yet? The question is known as the P versus NP problem because the class of problems that can be solved in polynomial time is called P. P versus NP is one of the hardest open problems in maths. Anyone who manages to answer it will win $1 million from the Clay Mathematics Institute (see How maths can make you rich and famous). Not everyone agrees, but most mathematicians seem to think that P is not equal to NP: this would mean that NP problems really are very difficult, they cannot be solved in polynomial time.
![Lock and key](http://plus.maths.org/content/sites/plus.maths.org/files/istock_000020338624xsmall.jpg)
Answers to NP problems can be used as the key to encrypted messages.
And there's another twist to the story: any problem in the NP class can actually be reduced to the decision version of the travelling salesman problem. This means that any algorithm that solves the decision travelling salesman problem can be translated into one that solves all other problems in the NP class. So imagine you find a polynomial-time algorithm for the decision travelling salesman problem. This would then mean that every problem in NP could be solved in polynomial time, you would have proved that P=NP and could go and collect your $1 million. (And the same would be true if you found such an algorithm for the harder, general version of the travelling salesman problem.)
But there are other implications too. Problems from the NP class are often used in cryptography, for example in the RSA system that's used to make internet transactions secure. Essentially, the answer to an NP problem (say the prime factors of a large number) is used as the key you need to decode a message. The fact that there are no known algorithms to solve NP problems quickly means that the key is very hard to crack. (See Safety in numbers for more.)
So imagine you did manage to find an efficient algorithm to solve the travelling salesman problem. You'd get your million dollars, a key to the world's most secret codes and your life would probably no longer be safe. Someone should make a movie about this...