What an awesome book! P-NP is essentially the question of whether we can find solutions quickly if we can define or know there is a solution quickly-- in layman's terms, it means we know, and then can solve, the traveling salesman problem in "P" -- polynomial -- rather than exponential or infinite time, or not at all. (MAHDI emailed and corrected this by saying: "The second sentence is wrong. P-NP is whether we can find solutions nearly as efficiently as we can verify them. The statement that we can find solutions if we can know there is a solution is a known fact and an easy exercise to prove").
There are a lot of technical books on the topic, but this is the first recent book that explores the golden ticket (finding the ONE in your batch of many that will allow you into Willy Wonka's factory tour) in layman's terms, but without talking down to the reader, and covering and focusing on all the aspects of the question. "How not to prove that P does not equal NP" as the author says, is an example of the complex and convoluted logic that's needed to explore the field of computational complexity.
Most authors, including this one, use public key crytography, factoring, etc. as examples of the "good" things about intractable problems, yet they also point out that if you could solve this problem, all the other millenium prize problems would likely also fall before you! That's more than $5 million US, so this book is definitely worth a careful read! (Ok, little tongue in cheek). The current "go to" text on the topic, from 2010, is Goldreich's
P, NP, and NP-Completeness: The Basics of Computational Complexity
-- which takes a kind of "text" approach, with problems, exercises, etc., and is a lot more technically oriented (interpret: dry) than Fortnow.
Contents include: The Golden Ticket, The Beautiful World, P and NP, The Hardest Problems in NP, The Prehistory of P vs. NP, Dealing with Hardness, Proving P does not equal NP (which this author believes), Secrets, Quantum, and The Future.
This book is truly FUN and READABLE-- Fortnow peppers every page with anecdotes, examples, side stories, cartoons, diagrams, and an amazing array of connections. Past explorations couldn't even have asked if it's possible to scan for the largest Facebook friends lists, because Facebook didn't exist during most of the past P/NP books frames!
If you want a more general intro to computational complexity, Neil Johnson's little triple reprint from 07 to 2012 is outstanding:
Simply Complexity: A Clear Guide to Complexity Theory
, and is under 10 bucks. For an exploration of how P/NP fits with the other current millenial problems, an outstanding new book is Ian Stewart's
Visions of Infinity: The Great Mathematical Problems
. To go a level higher, and see how computational complexity fits more generally in Systems Science and systems thinking, Flood's 2010 book is a gem:
Dealing with Complexity: An Introduction to the Theory and Application of Systems Science (Language of Science)
.
NONE of these, however, are as gentle an introduction, with as complete and detailed coverage, as Fortnow. This is a must have if you have any interest in the biggest and toughest and perhaps most important problem of our age. The icing on the cake is the really fun read of a really dry topic!
EMAILERS-- update: For those who want more math on complexity than Fortnow gives, but not beyond advanced undergrad, check out this truly undiscovered gem by Sole:
Phase Transitions (Primers in Complex Systems)
.
Library Picks reviews only for the benefit of Amazon shoppers and has nothing to do with Amazon, the authors, manufacturers or publishers of the items we review. We always buy the items we review for the sake of objectivity, and although we search for gems, are not shy about trashing an item if it's a waste of time or money for Amazon shoppers. If the reviewer identifies herself, her job or her field, it is only as a point of reference to help you gauge the background and any biases.
Enjoy fast, free delivery, exclusive deals, and award-winning movies & TV shows with Prime
Try Prime
and start saving today with fast, free delivery
Download the free Kindle app and start reading Kindle books instantly on your smartphone, tablet, or computer - no Kindle device required.
Read instantly on your browser with Kindle for Web.
Using your mobile phone camera - scan the code below and download the Kindle app.
Something went wrong. Please try your request again later.
Frequently bought together
Customers who viewed this item also viewed
Page 1 of 1 Start overPage 1 of 1
About the author
Follow authors to get new release updates, plus improved recommendations.
Top reviews from other countries
RTG
No alcanza todo lo que puede llegar a ser este tema
Reviewed in Spain on July 21, 2014