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:

REVIEW OF SECOND EPISODE OF NUMB3RS USE OF P vs NP.

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.

7 comments:

  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.

    ReplyDelete
  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.

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

    ReplyDelete
  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).

    http://www.pbs.org/wgbh/nova/sciencenow/

    ReplyDelete
  5. Mohammad Al-Turkistany, PhD Candidate, University of Florida4:27 AM, March 24, 2005

    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...

    ReplyDelete
  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:

    http://www.qeden.com/

    ReplyDelete
  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.

    ReplyDelete