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 steps to solve the problem for 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 steps to solve the problem for places. Then ten places would require 1,024 steps and 20 places more than a million. This is rapidly exploding exponential growth.

The functions 2ⁿ (black), n³ (red) and n² plotted against n. You can see that 2ⁿ grows fastest for larger n.

Mathematicians have a clear idea of what they mean by a "reasonable" amount of time in this context. Expressions involving powers of , such as , or are called polynomials in . An algorithm is deemed efficient if the number of steps it requires grows with the number in the same way, proportionally, as some polynomial in grows with . That can still give you pretty rapid growth, especially if the power of in the polynomial is large, but at least it’s not exponential. An algorithm which fits this bill is called a polynomial-time algorithm.

So is there a polynomial-time algorithm for solving the travelling salesman problem? The answer is that nobody knows. Nobody has managed to find one yet, and nobody has been able to prove that there isn’t one either. So let’s make the problem a little easier: rather than asking for the shortest route, let’s ask if there is a route visiting all the places on your list that’s shorter than some number we’ve previously specified. This is called the decision version of the travelling salesman problem because it’s got a yes/no answer. Unfortunately it’s not known if there’s a polynomial-time algorithm to solve the decision version either, but at least there’s one bit of good news. If someone were to give you an answer to the problem, a route they claim is shorter than , then it’s really easy to check whether it’s true.

The collection of all decision problems for which a possible answer can be verified easily (in the sense that there’s a polynomial-time algorithms for checking the answer) has a name: it’s called the NP class. Another problem in that class is how to factorise large numbers into primes, for example working out that

Once you know the prime factors of a number it’s easy to check that they are correct, you only need to multiply, but nobody knows of any polynomial-time algorithms to find these factors in the first place.

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.

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...