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.

Pointing and laughing.

It is the next-to-last day of finals week.  A student in the next room is taking his final for the directed study we did this semester.  He did fairly well in the course, so I am expecting a pretty good score on the test.  The rest of my work is as close to caught up as it generally gets.  I spent some of this week sorting my accumulated things-to-do into two piles:  "Do it NOW"  and "It could wait until after Christmas."  Almost everything in the "Do it NOW" pile is done, so I'm feeling pretty good.   As it was in my previous job, the administrative work takes more time than the school says it ought to. 

In the meantime, when I get a few minutes to think about things other than work or other day-to-day life tasks, it is great to think about my retirement plans.  Now that I know when I am retiring (next summer), and where I will be going (back down south to my home state), I can think about what I will be doing.  I have a very long list of things I would like to do!   A friend who recently (a year ago?) retired told me he was still adjusting.  My cousin has also been retired about a year, and she told me she has still not adjusted.  With so many things I want to do, I believe it will  take me about a week to adjust.  Maybe not that long!  Maybe 45 minutes. 

In a conversation last week at a Christmas get-together, the subject turned to the upcoming Mega Million lottery.  One of the guys said that if he won a big lottery sum, his plans were to point and laugh (I assume at the rest of us poor stiffs who did not win.)  I like that image!  I plan on doing pointing and laughing next summer.