The Travelling Santa Problem

Why is the annual Father Christmas world tour ‘NP-Complete’?  What is ‘NP-Complete’ anyway?  In fact, what’s ‘NP’ even?  And why can only Santa do it?  And what’s a ‘Decision Elf’?  And just how awesome is Rudolph’s nose?  What’s ‘Inspirational Magic’?  This and so much more you didn’t know about the annual Christmas Eve ritual …

We all know the problem well enough …  Father Christmas has to travel around the world, visiting all the good girls and boys, in a single night, and return to where he started at the North Pole. Sounds like a tall order!  Can it be done?

Well, he seems to manage it so the answer must be ‘Yes‘ but how?  OK, he’s obviously got some very fast reindeer, a high-spec sleigh and a magic sack (so he doesn’t have to keep going back to base to refill it) but how does he know which way to go?  How does he know the best way to go?

Estimating how many stops Santa has to make isn’t straightforward.  Not all the children have been good and some will live together so a simple headcount (even if we could do that) doesn’t quite answer the question.  However, it has to be hundreds of millions at least and a round figure of a billion will be about the right order of magnitude today.

Modern day computer scientists study this challenge under the guise of the Travelling Salesman Problem (TSP).  They don’t realise that the original ‘Travelling Santa Problem’ (also the TSP of course) dates back hundreds of years.  In the modern version, the salesman has to find the best way of visiting n cities to peddle his wares.  He might have an n of a few dozen cities on his itinerary over a few weeks.  In the original, Santa has n = 1,000,000,000 homes and just one night.  (True, n would have been a lot smaller when he first started his job, but still huge.)

A quick bit of theory; not too much … In either TSP, there are n ways of choosing the first stop, then n-1 ways of choosing the second, n-2 for the third, and so on …  When there are only three stops left, there are 3 choices, then 2 choices for the remaining two, and finally just 1 choice for the very last.  That gives a total number of different ways of visiting the n places of

n  ×  n-1  ×  n-2  ×  ………..  ×  3  ×  2  ×  1,   which we write as n! (n factorial).

Factorials get very big very quickly.  10! is over three million, 70! blows calculators with two-digit exponents; 1,000,000,000! just can’t be imagined, even by a computer.  Modern day computer scientists haven’t solved the TSP for the salesman’s profit.  How on earth did Father Christmas manage it for free all those years ago?  Well, the simple answer is he had some very clever elves and a very special reindeer called ‘Rudolph’ but, to see how that helps, we’re going to have to briefly dive back into the theory …

Like most ‘normal’ people, computer scientists like problems that are easy and dislike ones that are hard.  Roughly speaking, in algorithmic terms, ‘easy’ means the problem can be solved in polynomial time (which essentially means not too many steps of a program to run) and ‘hard’ means it can’t (so probably lots of program steps).  Some problems belong to a nice, easy class, which we call P, of problems that can be solved in polynomial time.  Unfortunately, the TSP doesn’t seem to belong to P.

If a problem itself doesn’t apparently belong to P then we start clutching at straws somewhat by trying to find something that we can do in polynomial time. We define a new class of problems, NP, meaning ‘non-deterministic polynomial’ time in either of the following ways:

1. Although, all practical algorithms and programs behave predictably – ‘deterministically’ (and it’s hard to build computers any other way), perhaps we can at least imagine an algorithm/program that makes random – but ultimately correct – decisions at each step.  If a problem can be solved in polynomial time by this type of ‘miracle algorithm’, then we can say it’s in NP.
2. Alternatively, suppose someone offers us a solution to the TSP (good or bad).  How easy is it to work out how long it will take?  Assuming we have some idea of times/distances between individual points, we can trace out the tour on paper and calculate the total time.  We don’t have to try out all the tours, just add up times for the one we’re given.  If we can evaluate a given solution to a problem in polynomial time then we can also say it’s in NP.

So we actually have two definitions of the class NP and it’s far from obvious that they’re saying the same thing.  OK, time to get back to Father Christmas, his elves and his reindeer …

The first year, Santa got the job of taking presents to all the world’s good boys and girls, he was pretty worried.  He knew he had good equipment, including fast reindeer and a magic bottomless sack, but there were just so many possible orders in which to visit the children (so many possible ‘tours’ of the stops) that he just didn’t have a clue how to do it.  In fact he didn’t even know if it could be done.  Was it even possible to make the world tour in the one night, even if he could find the best tour?  Even today, modern computer scientists ask essentially the same questions and have the same difficulties: What’s the best solution for a given TSP example and can it be managed below a certain value?  The long and the short of it is that no-one’s found any approach that’s very much better than trying out all the possible tours.

But this is where Santa’s elves came in; elves are hard-working, enthusiastic and incredibly fast and efficient.  In the beginning, a single ‘Calculating Elf’ looked at all the possible tours over the first few months of the new year and worked out the whole tour length for each one.  The elf did this by looking at each ‘flight’ between any two stops for good children and adding up the distances for the flights to get the distance for the whole tour.  (A few million flights and a good few billion, trillion, quadrillion … tours isn’t much for a dedicated elf.)  The Calculating Elf then picked out the best (shortest) one and reported it to a second elf … the ‘Decision Elf’.

The role of the Decision Elf was more focused: to look at any suggested tour and calculate the time taken to travel it.  In particular, could the tour be completed in a single night?  In practice, at first, this only really applied to the ‘best’ tour, which the Calculating Elf had supplied.  Could this best tour be completed by Santa on Christmas Eve?  Certainly, to begin with, it generally could; and the Calculating and Decision Elves between them had usually solved the TSP for that year by Easter.  All Santa had to do on Christmas Eve was to follow their route, worked out several months earlier.  So, although the Calculating Elf was pretty convinced that the TSP wasn’t in P (because there were so many tours to consider and no obviously better way of doing it), the Decision Elf knew it was at least in NP (because it was simple enough to work out if a tour he was given was good enough – definition 2 above).

However, over time, more and more children appeared on Santa’s list.  Not all were good, of course, but an increasing number were.  The TSP got more and more difficult to solve each year.  When the ten millionth stop appeared, for example, the TSP became 10,000,000 times bigger (n!).  The Calculating Elf worked harder and harder, longer each day, and found better ways of doing the sums to try to cope.  In fact, for several decades processing efficiency was doubled each year, forming a pattern known as ‘Mor’s Law’ (‘Mor’ being the Calculating Elf’s name).  Ultimately though, this doubling was never going to keep up with the factorial complexity of the TSP, which reinforced Mor’s conviction that the TSP wasn’t in P (although didn’t actually prove it).  By comparison, the Decision Elf, ‘Boz’ remained happy enough that it was in NP.

Fortunately, Santa had more than two elves … in fact, lots and lots of elves; and together they devised a cunning plan.  Each of several Calculating Elves now took a large number of the possible tours, arranged and divided by the first few individual flights and worked out the whole tour length for each one as before.  Each Calculating Elf then took the best tour they’d found to an Elf Council in which the individual winners were compared to find the overall winner – the best possible tour.  This best tour was then finally reported to Boz, the Decision Elf, to pronounce – as before – whether Santa would be able to manage the tour on Christmas Eve.  He still could, as it turned out.

But the number of good children kept growing; the TSP kept getting bigger.  Santa now had as many elves as he could fit into his North Pole factory; there simply wasn’t room for any more.  Also, it was getting difficult for Mor, now promoted to ‘Chief Calculating Elf’, to manage the huge team of Calculating Elves, who were soon squabbling over resources: where to work, when to report results, and to whom, etc.  Things became so heated that the snow on the roof was beginning to melt.  The Elf Council became deadlocked.  ‘Mor’s Law’ was breaking down.

The Decision Elf, Boz, tried to help by suggesting that it might not be necessary to find the best solution to each year’s TSP to work with.  If a likely candidate that might work could be identified at any time in the year, then Boz would consider it there and then to see if it would do.  That is, could Santa complete the given tour on Christmas Eve?  If he could, then the problem was at least ‘partially solved’.  A better (shorter/quicker) solution might turn up later but, if it didn’t, there was no need to worry; Santa would at least have a working route to take.  At first, an initial feasible route generally showed up in January, then February, then March, then …

And the problem kept getting bigger.  One year, the first feasible tour wasn’t found until July, with just two better ones being found in October.  The next year, the only feasible tour appeared in September: nothing better followed before the Calculating Elves ran out of time.  At this point, Father Christmas knew he was soon going to be in trouble.  Mor performed some complexity analysis and predicted that the following year it was likely that no feasible solution would be found; there almost certainly would be some but it was improbable that any could be identified in the year leading up to Christmas Eve.  Fanciful new ideas, such as ‘Quantum Elf’ technologies, were proposed but any practical implementation seemed a long way off.  Christmas Future for the good girls and boys looked bleak.

And that’s how it turned out.  Despite working harder than ever before and devising new, efficient internal structures, by mid-December the next year, Mor’s team hadn’t identified a single tour to satisfy the Decision Elf.  Each month, the current best solution had been sent to Boz for analysis but every one had been rejected as taking too long.  It was looking like Santa would have no route to follow that would get the job done on Christmas Eve.

Then the miracle happened …

One evening, two days before Christmas, Santa was out feeding the reindeer when he overheard them singing a curious song …

“Rudolph, the red-nosed reindeer
had a non-deterministic nose
and if you ever give him a combinatorial optimisation problem
each individual correct step it shows”

(A much simplified version of this rhyme survives to the present day although the original meaning has been entirely lost.)

Although feeling pretty miserable at this point, Father Christmas couldn’t help but be intrigued.  He asked what the strange words meant.

All talking at once, and in a very confused way, the reindeer eventually explained that the song was from old folklore; it described a mythical reindeer from Lapland, who was possessed of what was generally known as ‘old magic’.  When pressed further, Dancer – just about the most lucid of the team at that point, having not yet partaken of his sherry-oats – told Santa the tale of Rudolph and his red nose, which was supposedly capable of ‘Inspirational Magic’.  ‘Inspirational Magic’ was apparently the ability to always choose the correct option from a number of choices … a natural, non-deterministic problem-solver.

The news hit Father Christmas like a clap of thunder.  He knew instantly that Rudolph’s magic was what he needed.  He hitched up his reindeer team to the sleigh (always somewhat risky after supper) and set course for Lapland.  (Raw speed itself was never an issue for Santa, remember.)

They found Rudolph meditating quietly in a field of snow.  Santa jumped from the sleigh almost before it had landed, rushed up to the startled reindeer and implored:

“Rudolph with your nose so bright
won’t you guide my sleigh tonight?”

(This part of the rhyme remains intact today although ‘bright’ is now misinterpreted; it clearly means ‘intelligent’ in this context, not ‘luminous’.)

 Although he wasn’t going to let on, Rudolph had pretty much had all he could take of standing in a field for the past few centuries so he readily accepted the job.  Overjoyed, Santa and his new, enlarged team of reindeer returned to the North Pole in the nick of time and loaded the sleigh up with presents.  With Rudolph at the front, they got ready to depart for their world tour.

“So where are we going?” Santa asked as they took off.  Rudolph told them the first stop.

“Then where?” cried Prancer.  Rudolph shrugged his shoulders.  “I won’t know that until we’ve made the first stop,” he grinned.  This worried Santa at first but he soon got the picture.  At each stop – and not before, Rudolph was able to use his nose and its inspirational magic to work out where to go next.  Stop by stop, step by step, flight by flight, they visited every good boy and girl in the world and returned home to the North Pole before Christmas Morning.  Making his inspirational, non-deterministic choice at each step, Rudolph had not only found a feasible solution to the TSP, he’d found the best solution.  (He’d solved an NP problem by definition 1 above.)

“Then all the reindeer loved him
and they shouted out with glee
Rudolph the red-nosed reindeer
you’ll go down in history!”

And of course he did.  But first, the night’s adventure was reported back to the Decision Elf.  Boz examined the sleigh’s flight recorder and confirmed that the route they’d taken was indeed a feasible tour … but of course everyone already knew that.  The TSP now satisfied both definitions of an NP problem: Rudolph had been able to find the solution non-deterministically (definition 1) and the Decision Elf had been able to validate the solution deterministically (definition 2).  Rudolph taking each step of the the optimum tour correctly in practice and Boz adding up the times in the same order in theory obviously had the same complexity and the two definitions made sense.  Everyone was happy: Santa, his reindeer, the elves and – most important of all – all the good children.

And they remain so to this day thanks to Rudolph, who is still the only example of a truly non-deterministic optimisation algorithm in the world.  Santa still needs him because no-one’s ever found a deterministic solution to the TSP and most folks suspect that there isn’t one.  (So the TSP probably isn’t in P but we can’t be sure.)  If a ‘detrministic Rudolph’ was to be found then the original Rudolph could retire but that doesn’t look very likely and – truth be told – he doesn’t really want to.

Modern day computer scientists now know of many problems that are similar to the TSP in the sense that they don’t have a Rudolph for them although they really need one to solve them.  These problems are known as ‘NP-Complete‘.  A deterministic Rudolph for any one of them would, in fact, work for all of them but they haven’t found one for themselves – but nor have they proved there can’t be one.  Of course, the real Rudolph is still non-deterministic … inspirational … magic … and he works only for Santa … not the computer scientists.

Merry Christmas!