Tuesday, February 08, 2005

Guest Post on Numb3rs P vs NP Episode

Suresh has been doing a fine job reviewing the Numb3rs episodes. Nevertheless Bill Gasarch wanted to write a guest post on the P versus NP episode which was the second episode broadcast and not the fourth as I had previously mentioned. But first my comment to Charlie: Don't let your brother mess up your priorities. Go back to solving P versus NP. So what if a few bank robbers get away?

Now on to Bill's Guest Post:


This is the `P vs NP' episode.

"Are you still working on that P vs P thing"

"Its the P vs NP thing"

They mentioned P vs NP ALOT of times.

PROS: ANY mention of our favorite problem on TV is good. This may be the first mention of P vs NP on an entertainment show since Homer Simpson fell into the third dimension where there were all kinds of equations floating around in the background including P = NP.

CONS: Wasted Opportunity. They made NO attempt to explain the problem. Could they have? Trying to color a map with 3 colors might be the problem easiest to explain. Or TSP. Might be hard to tie that to a crime, but minesweeper is also contrived. For that matter, could they have explained minesweeper better, and add something like "One way to solve it is to look at all possibilities. Even with really powerful computers, that could take to long. We want to know, is there a faster way?" I would not even try to explain NP or `checkability' I would just say that here are problems we can solve by looking at all possibilities, and we want to know if we can do substantially better.

ODD POINT: They mentioned a few times that it was `unsolvable' What did they mean? Options-

  1. Charlie was trying to prove P=NP and this is unlikely to be true
  2. Charlie was using techniques from recursion theory that likely to not work because of the oracles. (the what?)
  3. Charlie was using proofs that naturalize, which won't work because of the results of Razborov and Rudich (Judd Hirsch: So use unnatural techniques)
  4. The problem is independent of PA
  5. The problem is independent of ZFC
  6. The problem is just very very hard.
Likely they meant 1 or 6 (SARCASM ALERT: 2-5 were not meant to be taken seriously). But they should have spoken more clearly about this.

PRO: They do (in general, not just this episode) show Math in a good light and show Mathematicians in a good light.

PREDICTION: Will be canceled within 1.5 years. Don't need Charlie's math to predict that.


  1. I don't get happy when CS or math appears like this on TV, on
    the contrary! Everyone knows that TV series are an unreliable source
    of any kind of information. Moreover, I don't watch TV series myself,
    including this one...
    I would be really glad if CS or science in general were discussed in
    journalistic programs, or even talk shows: maybe an interview with some
    high profile mathematician or CS guy - that would be great. Programs
    such as "cosmos" (in the 80s) are also an excelent way of discussing some
    science, and still fun to watch.

  2. I agree that any press is good press, but the real question is: how will this improve the reception I get when I tell a girl at a party that I study Theory of Computation? The only people watching TV on a friday night are under 12, already settled with a family, or nerds like us. At least the show might be reaching our youth though, and we can promise a better America to our children.

  3. Anything that lets the general public know we do more than "work on computers" is a good step.

  4. Just in case you're unaware of it, there is this new show on PBS called ScienceNow and it's hosted by Robert Krulwich. He's made some pretty fascinating TV shows about science with Ted Koppel (e.g. Brave New World and Nightline).


  5. I think people are stuck because they are not asking the question correctly. Remember proving the undecidability of the Halting Problem was delayed until people formally defined the notion of Algorithm. More on P vs NP soon...

  6. In case you're interested, I started up a wiki about the subject of this (and the other millennium problems). Take a look, and feel free to contribute:


  7. I'm glad your prediction was wrong. I just found this show recently, so I would have missed out on it! Hopefully they will keep it around for a while.

  8. Very happy this prediction was wrong as well. This show went on for 6 seasons (from 2005 to 2010). I began watching in 2007. It would be cool if they had some sort of reunion show or made for TV movie; but, I predict that a reunion episode will never happen. Definitely recommend watching the 2016 movie, "The Man Who Knew Infinity" about Ramanujan (Numb3rs character was named after the man in this bio-pic).