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!

Saturday, 5 May 2012

Ep 145: Teleportation

Is teleportation possible in the real world, or only in the world of science fiction?

In this very special episode, Dr Boob takes the reigns and leads us on a journey through teleportation, whether or not physics allows it and even if it does, can we technologically achieve it? What are the implications if we recreate someone in another spot - what about their soul? Does such a thing exist? And even if you can technologically achieve this, is it possible to reanimate a copy of someone? What do you do with their original version, if you have simply copied them? This could be considered cloning, which brings in ethical questions.

Perhaps wormholes could be a solution to this problem, but we haven't found any yet - however they are, as physicists like to say, theoretically possible.

Tune in to this very entertaining episode (and I can say this without any false modesty as Dr Boob did it all himself) here.

If you'd like to hear more of Dr Boob on this podcast, check out our past joint episodes, mostly on the science of superheroes. He's also on twitter, so come and follow him, he needs friends!