Who'd a thunk it!? …that somebody could write an engaging, fascinating account of the P vs. NP Millennium Problem for a mass audience? Moreover to have done so without ever too-technically defining either P or NP, nor introduced much of the jargon or mathematics one might expect such a treatise to require! Hats off to Scott Fortnow (a blogger at "Computational Complexity") for doing it!
P vs. NP is one of the seven famous Clay Institute Millennium Problems for which one earns a cool $1 million for simply finding a solution (… but of course "simply" is NOT the operative word! -- thus far only one of the problems, the Poincare Conjecture, has been solved… and, ironically, the solver, Grigori Perelman, refused the prize money!).
Fortnow's book has been well-praised by reviewers, and oddly it reminds me a bit of Jason Rosenhouse's "The Monty Hall Problem." Both books are uncannily the same size and shape (and about the same number of pages), but more importantly, just as Rosenhouse did a wonderful, meticulous, intricate job of explaining the Monty Hall Problem (and its many nuances) to a lay audience, Fortnow does a similar job for P vs. NP, with a book that is, surprisingly, a bit of a page-turner.
I suspect I could read Fortnow's work 3-4 more times and each time take away a little more knowledge and understanding of the depth of P vs. NP, such is the richness of the volume. The content and implications of the book crosses boundaries of computer science, philosophy, math, logic, complexity, and number theory.
For any who don't know, P problems are those that can essentially be solved relatively quickly; i.e. "efficiently" (via a computer at least), while NP problems cannot be solved in any reasonable amount of time, even with the aid of computers, even though proposed answers CAN BE checked quite quickly. And the conundrum is to discover if these two classes of problems are in fact one-and-the-same, i.e. P = NP… or, as MOST researchers believe, do P and NP problems represent distinctly separate categories. To the uninitiated it may seem like a question of hugely abstract or narrow interest, but as Fortnow notes, "Determining whether P = NP is the most important question in computer science and perhaps in all mathematics." [bold added] Again, most believe P ≠ NP, but this too is exceedingly difficult to PROVE.
The so-called "Travelling Salesman Problem" is likely the most well-known of the NP problems… given say a few hundred cities to visit, find the shortest, most efficient route for visiting them all (…might seem to some like a straightforward problem for a modern-day computer to solve… but, it ISN'T! there simply is no algorithm, nor brute force technique, to solve it in a human time-frame.
The initial chapters of the book employ made-up examples to communicate the nature of P vs. NP. Often I prefer the use of 'real-life' type examples over invented ones to get across mathematical or scientific ideas, but Fortnow's concocted versions are so good and entertaining that they serve his purposes well. Chapters 4 and 5 go into some of the history of P vs. NP… normally, a book might start off with the historical part, but I think Fortnow succeeds in drawing you into the whole subject with the introductory chapters, and only then putting forth the history which may be a little dry or tedious and not the best lead-in to the topic.
Chapter 7 touches on Gödelian thought as well as the "halting problem." Most folks are familiar with the paradoxical, self-referential sentence, "This sentence is not true." Fortnow introduces a variation, "There is no proof that this sentence is true," to help explain how Gödelian self-reference demonstrates that there exist sentences which may be known to be true, yet are unprovable (if the prior sentence is false, then there IS a proof of the sentence, but if there IS a proof that the sentence is true, then it CANNOT be false! And vice-versa IF the sentence IS true, then, by its own admission, there is NO PROOF of its truth). In the end though, Fortnow notes that "this paradoxical approach to P versus NP seems doomed to fail, at least as a direct attempt at showing P ≠ NP."
Chapter 8 is on cryptography, one of the most significant real-life areas that would be affected if P were ever shown to be equal to NP (in which case code breaking, including breaking RSA encryption, could be done with ease).
In Chapter 10 we learn about NC, 'Nick's Class' of problems, another category within complexity theory, that may or may not be equal to the NP category of problems. Such ideas may be old-hat for those well-steeped in computer science, but are a new arena for the rest of us.
One update I learned from the book is that Vinay Deolalikar's claimed 2010 proof that P ≠ NP is apparently no longer in play. Last I'd heard (but I haven't followed the story that closely) Deolalikar was still trying/hoping to patch the various objections that critics voiced concerning his 'proof.' Apparently, though there were (not surprisingly) fatal flaws he could not overcome.
In fact, according to Fortnow, "We are further away from proving P ≠ NP then we ever were. Not literally, but in the sense that there is no longer any obvious path, no known line of reasoning that could lead to a proof in the near future."
Fortnow does mention that the field of "algebraic geometry" is currently the best candidate for possibly making progress on the problem. And he does indicate toward the end that he believes eventually P will be shown to not equal NP "…but it might take twenty or two hundred or two thousand years."
This is yet another splendid book from Princeton University Press, on a topic rarely treated in book-length form for the layperson, and for most of us a valuable, mind-stretching offering.
(Princeton Univ. Press has a transcribed interview with Fortnow about his book here: http://press.princeton.edu/releases/m9937.html )
ADDENDUM: Scott Aaronson, who is far more expert than I to review the Fortnow book, now has his own very positive review up over at his blog here:
http://www.scottaaronson.com/blog/?p=1293
No comments:
Post a Comment