The Golden Ticket: P, Np, and the Search for the Impossible

As i retired at 55, i found a hobby trying to solve P vs NP for 14 years now. It took me 9 years to found a promising angle of attack. After another 5 years to refine the algorithm. If there is a solution i will find it maybe in 3 to 4 years but who knows. While working on the algorithm i bought this book and i liked it very much.

I really like this book as it explains in layman terms the details of the p vs np problem and has seperate chapter on implications of p=np

yeah

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.

Muy decepcionante. El libro parece tratar en principio sobre el problema de P y NP, pero lo que el autor tiene que contar sobre la materia es tan poco que hay decenas de páginas de relleno. Hay partes de relleno muy divertidas e interesantes, como la completísima historia de ficción en la que se demuestra que P=NP y por tanto todo problema computacional puede reducirse a otro problema resoluble en tiempo polinómico. El autor hace en esa historia un fantástico ejercicio de imaginación comparable, creo al de alguien a quien le pidieran en 1970 qué pasaría si todo el mundo tuviera a acceso a internet.Pero luego nos llegan las disgresiones, la introducción a los algoritmos de cifrado (sin relacionarlos mucho con P=NP), la criptografía cuántica (para la que de momento no hay mucho armamento algorítmico puesto en producción)... y otras cosas que me hacen echar de menos el tema principal del libro. Un poco disperso, vaya. Lo que cuenta es interesante pero yo esperaba algo más técnico y más centrado en el tema principal.