Skip to content

Where are the Movies on P=NP?

February 27, 2009


Why not movies about the p=np question

images27

Dick Karp and I first meet at the IFIP Congress in Stockholm in the August of 1974. I recall the meeting vividly. When I meet him, I was a freshly minted assistant professor at the Yale Computer Science Department. Dick was quite friendly and gracious towards me and I have ever since considered him a close friend. Actually the truth is I was a “Gibbs Instructor”: I had a reduced teaching load, only a two year contract, and a small travel budget. I also was paid {10} percent less than my colleagues–David Dobkin and Larry Synder who were real assistant professors.

Another reason I recall meeting him after so many years, was that during the conference Richard Nixon resigned as the 37{^{th}} president of the United States on August {8^{th}}. As I watched, from my hotel room, a Swedish TV announcer said that Nixon had “avgången”. I know no Swedish, but I could see that this looked like “ausgang” which is exit in German. Great, Nixon was gone.

Back to the present, while at least this century. A few years ago I gave a talk at the opening of a new research center at Georgia Tech. The center is called ARC and stands for “Algorithms and Randomness Center”. ARC was created by Santosh Vempala and has been a terrific success. We often call it the ARC center which is of course a bit redundant since that translates into “Algorithms and Randomness Center Center”, but that the way things go.

My talk was on “Algorithms are Tiny” which I discussed in an earlier post. The point of the talk was that algorithms are like equations. They are small, yet can have huge impact. They are small, yet can create entire new industries. They are small, yet can change the world. To paraphrase Einstein: “Algorithms (he said equations) are more important to me, because politics is for the present, but an equation is something for eternity.” Just as {E=MC^{2}} changed the world, I argued that there could be an algorithm that fits on one page for SAT or for factoring. Such a single page could change the world.

At the end of the talk I got the usual technical questions. Finally, Dick raised his hand and I called on him. He said if I was right about algorithms being “tiny”, then where were the movies? Where were the movies about the discovery of a new algorithm that changes the world. Indeed where are they?

The closest there has been is probably the 1992 film “Sneakers” that starred Robert Redford. Len Adleman was the technical advisor on the film and worked not for money, but provided his wife could just meet Redford. His amusing recollections are here.

Open Problems

What a great question. I really had no good answer. I think this is a great open question. Shouldn’t there be some cool sci-fi type movie based on a story like this:

A computer scientist discovers how to factor. She gets into trouble with various people who either want to suppress her discovery, or to get it to break commerical systems to make money, or others who want to break military systems to attack the US. And there would also be a love story between her and some agent{\dots}

Perhaps I should stop blogging for a while and work on a screenplay. My daughter Andrea is visiting today from LA and she knows people who know people so I could get my story to the right people.

13 Comments leave one →
  1. February 28, 2009 3:23 am

    Hi Richard,

    You might enjoy watching the movie π – it’s not exactly what you’re looking for, but close.

    best regards,
    Martin

    • rjlipton permalink*
      March 1, 2009 8:34 am

      I have seen this movie. Its really great, so thanks for pointing it out…dick

  2. Fred permalink
    February 28, 2009 8:16 am

    An episode of the TV series “Numbers” called “Prime Suspect”

    http://en.wikipedia.org/wiki/List_of_Numb3rs_episodes_(season_1)

    tells the imaginary story of a mathematician who proves the Riemann Hypothesis and somehow manages to use his discovery to break cryptographic schemes. Needless to say, someone wants him dead…

    • rjlipton permalink*
      March 1, 2009 8:39 am

      I do not watch this show, so thanks for pointing out the connections (hats off to Jonathan and Fred). I will have to catch it now.

  3. Jonathan permalink
    February 28, 2009 5:51 pm

    Actually, the TV show Numb3rs had an episode where a person discovered some clever factoring algorithm, only to have his family kidnapped for ransom because of this.

  4. danupon permalink
    February 28, 2009 9:43 pm

    This reminds me of one episode of Numb3rs where a mathematician is believed to prove the Riemann Hypothesis and his daughter is kidnapped because of this. It turns out that the kidnappers wants to use his proof to break encryption algorithms. (I’m not sure I understand it well, but according to http://www-math.cudenver.edu/~wcherowi/mathmajor/archive/num3guide.html, it seems there’s no clear connection between the two things.)

    Even P vs. NP is mentioned from time to time in this TV show.

  5. March 1, 2009 4:00 pm

    Norbert Weiner’s novel “The Temptor” is about an algorithm that changed the world (that algorithm being, the theory of close-loop control). However, “The Temptor” was never made into a movie, as far as I know.

    Wired Magazine has an article this month titled “The Secret Formula That Destroyed Wall Street” … it seems to be essentially about the Black-Scholes equations and its sequels. About *this* equation, and the globally disastrous economic consequences of embracing it, there will be a movie, for sure.

    Military strategist John Boyd exerted a tremendous effect upon two generations of aircraft with a mathematical figure-of-merit he called “Energy Maneuverability”.

    Of the three, I think Weiner’s fictional analysis is the most thoughtful … the reason being that Weiner crafts his story to makes clear that (in Weiner’s view) the federative aspect of an algorithm is just as important (in the long run) as its mathematical aspects.

    Essentially this same point is made by William Thurston in an essay “On Proof and Progress in Mathematics” (if I remember the title right).

  6. March 19, 2009 1:27 am

    Please, can you PM me and tell me few more thinks about this, I am really fan of your blog…

  7. July 7, 2013 12:11 pm

    There is a recent independent film called “Travelling Salesman” which is exactly what you mention here. I’m looking forward to seeing it.

Trackbacks

  1. Savitch’s Theorem « Gödel’s Lost Letter and P=NP
  2. Hilbert’s 10.5th Problem « Gödel’s Lost Letter and P=NP
  3. The Travelling Salesman’s Power « Gödel’s Lost Letter and P=NP
  4. Independence Day | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s