*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?

Continue reading

4 Comments | tags: NP, NP-complete, Travelling Salesman Problem, TSP | posted in Algorithms, Computer Science, Mathematics, Philosophy

That looks like a hopelessly vague question, and it is unless we’re prepared to clarify it a bit. On the other hand, we already know there are some *impossible* problems so surely there are some that are just *hard*? Again, we’ll need to work out what on earth we’re talking about here. Let’s start with what we actually mean by a *problem* in a *computational* sense …

*(Be warned: There are one or two simplifications and liberties with precision in what follows; it’s well-intentioned but may upset the purist.)*

Well, actually, even *that* isn’t simple and there’s no absolute agreement on what a good definition would be. (We’ve seen previously that mathematicians and computer scientists don’t always see eye-to-eye.) It’s cheating a bit but it’s probably easier to give examples and this should work well enough for us. At least in the context of *computing*, these are all valid *problems*:

- Calculate
*2 *x* 4 + 9 – 3*
- If
*5 – x = 2* what’s *x*?
- Find the largest from
*5, 7, 1, 4, 8, 5, 2, 4, 8, 5, 2, 6, 7, 7, 3, 3, 2, 4, 3, 6, 7, 7, 6, 5, 4*
- Sort
*25, 44, 66, 72, 12, 45, 56, 90, 45, 69, 11, 10, 12, 42, 88* into ascending order
- Arrange
*1, 2, 3, 4, 5, 6, 7, 8, 9* into a magic square
- What’s the best way to get to Paris?

Continue reading

7 Comments | tags: Algorithms, Complexity, Complexity classes, Computational complexity, Easy and hard problems, Math, NP, NP-complete, P, Problem solving, Travelling Salesman Problem, TSP | posted in Academia, Algorithms, Computer Science, Mathematics, Philosophy, Programming