Sunday, 6 May 2012

Travelling Salesman - the Movie

Science in the movies is a topic we've looked at a few times here on the blog. But this one is for the pure mathematicians. Check out this preview to the upcoming flick "Travelling Salesman".

I love these kinds of films - overly melodramatic acting, a slight misrepresentation of the science behind the plot (which is OK by me as this is a movie), government conspiracies, and mysterious music. The name "Travelling Salesman" comes from the famous mathematical Travelling Salesman Problem in which a salesman needs to visit a numerous destinations and wishes to do it in the shortest time. Whilst this may seem to be a simple problem, it is one of the most studied problems in mathematics. The more destinations involved, the more difficult to solve and in general there is no algorithm that can find the best answer. Brute force methods (that is, computing every possible solution and then finding the best) are computationally difficult, and with too many destinations, impossible. Hence mathematicians often use heuristics which find good, although not necessarily optimal, solutions quickly.

The premise of the movie is that the famous P vs NP problem has been solved. I'm not a pure mathematician, so I'll do my best here... P problems are those whose solutions can be found quickly (in Polynomial time, hence the P). NP problems are those whose solutions can not be found quickly, but if somehow a solution is produced using some extra information, it is easy to check that this solution is the best one (in polynomial time). Solving these problems take Non-deterministic Polynomial time - hence NP. A good example to show this is a jigsaw puzzle - finding a solution may be very difficult (and it's probably most accurate to image a blind person doing the puzzle), but it only takes a quick glance to see if any solution is correct.

The question that mathematicians ask is whether P=NP - which means, are there algorithms out there that solve seemingly NP problems in polynomial time? We haven't found any yet and mathematicians tend to think that P does not equal NP, but there is currently no proof. Proving this one way or the other is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute and carries a US$ 1,000,000 prize for the first correct solution.

But why do we care? One of the reasons is that modern cryptography is based on the fact that P does not equal NP - this is the premise of the movie. Modern codes start with a pair of large prime numbers p1 and p2 and multiply them together to give  m=p1p2. The number m is released to the public, but p1 and p2 are kept secret. To crack the code you have to find p1 and p2, given the value of m. It turns out that finding the prime factors of large numbers (100+ digits) is exceptionally difficult, although checking an answer is very easy. It is thought to be an NP problem. But if indeed P does equal NP, this suggests that out there somewhere is an algorithm that could solve this problem in quick time, meaning that modern encryption codes are vulnerable.

They don't give too much away in the preview, but I suspect what happens is they prove P=NP, although the example of looking for something hidden in the desert seems like a P problem (you just check out under each grain of sand, which would be easy, although it's a nice illustration of the problem). We stretch the science here a bit - even if you prove P=NP, you still need to find the appropriate algorithm for the problem, which has never been done. But hey, it's a movie, and we don't pull Terminator up on its stretching of science!

There is a very good write up of the P vs NP problem over on Plus - check it out, it does a much more thorough job than I do!


  1. My favourite example of a problem in NP (in fact, it's NP-complete) is Sudoku. Enough people are familiar with Sudoku that you can get quite a lot across with that.

    (Of course, we're not just considering the order-3 Sudoku that we see in the newspapers, but a generalised order-n problem, but nonetheless, order-3 contains enough of the ideas to get them across to most people.)

    As with all problems in NP, checking that an answer to a Sudoku problem is correct is easy. Finding an answer is (believed to be) far more difficult.

  2. You mention that even if you prove P=NP, you still need need to find the appropriate algorithm for the problem.  Actually, one of the most interesting properties of the class NP-complete, of which the traveling salesperson decision problem belongs, is that if you find an efficient polynomial time algorithm for any single problem in this class, you immediately get a solution for ALL problems in NP.  If a proof of P=NP exists, it presumably would come in the form of a polynomial time solution to some problem in NP-complete, meaning that you do not actually need to find a solution to your particular problem.  The proof immediately gives you a fast solution to ALL NP problems.  This is part of why showing P=NP would be crazy exciting.  Showing P not equal to NP would be amazing, but no nearly as much so.