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.