Suresh has been doing a fine job
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?
- Charlie was trying to prove P=NP and this is unlikely to be true
- Charlie was using techniques from recursion theory that likely
to not work because of the oracles. (the what?)
- Charlie was using proofs that naturalize, which won't work because
of the results of Razborov and Rudich (Judd Hirsch: So use unnatural techniques)
- The problem is independent of PA
- The problem is independent of ZFC
- The problem is just very very hard.
Likely they meant 1 or 6 (SARCASM ALERT: 2-5 were not meant to be taken
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.