The Golden Ticket: P, NP, and the Search for the Impossible 1st Edition

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.

A rare popular science book about the P vs NP problem. The author takes care in using concrete examples and simplifying explanations as much as possible, though I think at times he makes it too simple. I especially liked that he included the history of how the problem developed on both sides of the iron curtain during the cold war. This book may be a nice read for people who don't have much of a science or math background, but for those who do I don't think they will get enough out of it compared with just reading some wikipedia articles.

Very interesting and powerful information.However some explanations are hazy enough that it sounds a little uncertain at times.Very particularly the author should review quantum mechanics and the “how” of so-called 'quantum teleportation' …. It doesn’t work as the author says, not at all.Still, extremely thought provoking in the areas the author is really conversant with.

Lance Fortnow's new book is an inspiring, accessible, and imaginative overview of P versus NP that everyone can read and appreciate, which until now has been conspicuously missing from the literature. Within the "folklore" of complexity theory, people have long uttered intuitive phrases to motivate P versus NP in passing, such as "P versus NP is asking whether creativity can be automated by computers." Fortnow takes these intuitions and expands them, like no one else has before: really imagining a world where P = NP, exploring the magic of computing in that world, and arguing why that world is unlikely to exist. He also discusses a historical account of the problem's origins in both the East and West, how people cope with P versus NP in practice, some past attempts at resolving P versus NP, the applications to cryptography, and the relevance of quantum computing. All this in less than 200 pages!There is an intellectual cost to the immediate accessibility of this book: for example, P and NP are never really formally defined. If you would like to *work* on P versus NP, or (less ambitiously) are looking for a technical overview of the problem, there are many available books to recommend such as Scott Aaronson's new Quantum Computing since Democritus or Sipser's classic textbook Introduction to the Theory of Computation. However, if you're just looking for a high-level explanation of why P versus NP is so important, Fortnow's book is a great place to start.

I started reading this book keeping my CS background in my mind and I lost the interest because of the vague descriptions of the problems and/or definitions but quickly I realized that this book is intended for non-CS audience. From that point onward I forgot that I'm a grad student in CS and started re-reading the book and I really enjoyed it. Now I use those terms/examples to describe/explain to my non-CS friends what I exactly do :-)