Movie Review: Travelling Salesman: P=NP

This is a movie about a subject that only computer people generally are familiar with, so a little background discussion is needed. For those of you in the know, forgive my oversimplification.

In computer science, the kinds of problems that could be attempted by a computer are divided roughly in to two categories.  Those that can be solved in a reasonable length of time are called "P".  Those for which it is possible to solve them, but they aren't put on computers because they would take MUCH too long, maybe thousand of years even on the fastest computers, are called "NP".  The title, Travelling Salesman refers to a famous problem in the second category.  The problem is simple to explain.  Suppose you are a travelling salesman who must visit a list of cities.  Knowing the locations of the cities and the distances between them, what is the shortest route you can take which will take you to every city?  For a short list of cities, it's not a bad problem.  But, when you start adding cities, soon it becomes unbelievably hard to solve, even on a computer.   Theoretical computer scientists spend a lot of time studying this problem. 

The basic premise of the movie, which doesn't become entirely clear until about the last 10 or 15 minutes, is that a group of 4 of the most brilliant computer scientists have been hired (for a LOT of money) by the NSA to find a way of solving "NP" problems.  According to the movie, they were successful!   First, they found a proof that there is a way to convert "NP" problems into "P" problems, and second, they created a new kind of computer processor that would do just that.  So, with the new processor, lots of problems that were previously unsolvable (like the travelling salesman problem) would become solvable. 

The technical details of the new processor are never really discussed, because that's not the point of the movie.  The point is that the NSA wants to keep it secret, and only let the government use it for its own purposes, and not let it out to the world.  The movie consists of the computer scientists sitting around a table with a representative of the NSA discussing the legal, moral, ethical, and social effects of such a move.  The computer scientists were not expecting this.  They thought their discovery would be of benefit to all mankind, not just the NSA. 

I think it is a fascinating movie.  There are lots of references to famous computer scientists and mathematicians, such as G. H. Hardy, generally recognized as one of the best mathematicians of all time.  One of the computer scientists is supposed to be among the extra-brilliant, on par with Hardy, and he is the one that turns out to be most bothered by the situation. 

Watch the movie and let me know what  you think.