We all know that the P=NP question is truly fascinating, but now it is about to be released as a movie. Can they be serious? Yes, a proof of P=NP would change the world as we know it.

A movie that features science and technology is always welcome, but is it not often we have one that focuses on computer science. Travelling Salesman is just such a rare movie. As you can guess from its name, it is about the Travelling Salesman problem, more precisely about the P=NP question.  Written and directed by Timothy Lanzone, and produced by Fretboard Pictures, it should premiere on June 16.

Is it science fiction? A difficult question because it is very much rooted in the contemporary world of cyber attacks and hacking. The idea is that modern cryptography depends on the idea that some problems are too hard to solve in a reasonable time, i.e that NP is not the same as P.

The plot of the movie is based on what would happen if some computer scientist managed to prove that NP=P.
In such a case, all of the codes based on NP problems would, in principle, be crackable. The effect of this might be to make all public key cryptography completely useless as the NP problems it is based on could be converted into problems in P and solved in a "reasonable" time.

As the blurb to the movie trailer says:

TRAVELLING SALESMAN is an intellectual thriller about four of the world's smartest mathematicians hired by the U.S. government to solve the most elusive problem in computer science history -- P vs. NP. The four have jointly created a "system" which could be the next major advancement for humanity or the downfall of society.

As the mathematicians are about to sign documents that will give the government sole and private ownership of their solution, they wrestle with the moral dilemma of how their landmark discovery will be used.

You can begin to see that there is scope for some drama, but rather than explain in any more detail it is better to just watch the trailer:

It looks like great fun and well worth watching.

However, even though the movie's description ends with,

The math is real. The implications are real.

which is true, the situation is much more complicated.

For NP=P to be a world changing discovery, it would have to yield low-order polynomial solutions. Having a solution that scales polynomially is no practical help if it still takes the age of the universe to actually compute.

It is a great story and I hope it raises public awareness of computer science so much that it becomes a cool subject to study.

More Information

Travelling Salesman Official Site

The Travelling Salesman’s Power

Related Articles

The Physical Travelling Salesman Challenge

NP-Complete - Why So Hard?

Minimum Spanning Tree

Computational Complexity

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, subscribe to the RSS feed, follow us on Google+, Twitter, Linkedin or Facebook or sign up for our weekly newsletter.