It's that time of the year again when Santa needs to think about how to deliver all those presents to the people on Earth. Unfortunately his reindeers are a bit weak this year, having suffered some severe bouts of flu, and he knows he can't ask them to travel more than a million kilometres in total. Is there a route around the Earth that visits all those cities, towns and villages he needs to visit, but is less than a million kilometres long?

A bit tired this year.

That, it turns out, is a very tricky question. One way of answering it would be to try out all different routes and work out their lengths. But since there are 7 billion people on Earth and he needs to visit every single dwelling that's totally unfeasible. It would take him until long after the Universe has ended to try all possible routes. Is there a clever algorithm Santa could use instead?

Obviously, the time it will take any algorithm to answer the question will depend on the number of places that need visiting — the more places, the longer it takes. So the question is whether there's an algorithm for which the time taken grows in a manageable, non-explosive way as the number of places grows — it's what complexity theorists call a polynomial time algorithm. If Santa were to ask such a complexity theorist he would find out that the class of all problems that can be solved in polynomial time has a name: it's called P.

Now Santa doesn't know if his problem of finding a route belongs to the class P. What's pretty obvious, though, is that if someone gave him a potential solution — a route they claim visits every place but is less than a million kilometres long — it would be easy to check whether that's true: he'd simply have to add up all the individual distances between places. A computer could do that quite easily. This means that Santa's problem belongs to a class of problems called NP. It consists of those problems for which potential answers can be checked in polynomial time, even though we might not know how to solve them from scratch in polynomial time.

But now suppose that Santa has a brainwave. Sitting down with a computer he constructs a polynomial time algorithm that finds the kind of route he is after. He would then have shown that his problem is not only a member of the NP class, but also of the P class. Amazingly, it would also hand Santa a polynomial time algorithm for all other problems in the NP class — because it turns out that his problem is a version of the famous travelling salesman problem, and that all the other problems in the NP class can be reduced to it. What is more, his algorithm would win Santa $1 million: the question of whether the P class and the NP class of problems are equal is considered one of the hardest in mathematics, which is why the Clay Mathematics Institute as offered $1 million to anyone who solves it.

Unfortunately Santa doesn't have the time to do any of this, and he's not a computer expert anyway. So he just takes an educated guess at what route to take and gets going, hoping for the best. It's a shame really because if he'd been able to show that P=NP he would have held the key to many of the world's secret communications, including everyone's bank details that are sent encrypted over the internet. This is because NP problems are used as the key for such encryptions, with the secrecy relying on the fact that the problems are very hard to crack. You can find out more in the Plus articles The travelling salesman and Safety in numbers.

Return to the Plus Advent Calendar