What do you think?
Rate this book
The Golden Ticket: P, NP, and the Search for the Impossible
The computer science problem whose solution could transform life as we know it
The P-NP problem is the most important open problem in computer science, if not all of mathematics. Simply stated, it asks whether every problem whose solution can be quickly checked by computer can also be quickly solved by computer. The Golden Ticket provides a nontechnical introduction to P-NP, its rich history, and its algorithmic implications for everything we do with computers and beyond. Lance Fortnow traces the history and development of P-NP, giving examples from a variety of disciplines, including economics, physics, and biology. He explores problems that capture the full difficulty of the P-NP dilemma, from discovering the shortest route through all the rides at Disney World to finding large groups of friends on Facebook. The Golden Ticket explores what we truly can and cannot achieve computationally, describing the benefits and unexpected challenges of this compelling problem.
The P-NP problem is the most important open problem in computer science, if not all of mathematics. Simply stated, it asks whether every problem whose solution can be quickly checked by computer can also be quickly solved by computer. The Golden Ticket provides a nontechnical introduction to P-NP, its rich history, and its algorithmic implications for everything we do with computers and beyond. Lance Fortnow traces the history and development of P-NP, giving examples from a variety of disciplines, including economics, physics, and biology. He explores problems that capture the full difficulty of the P-NP dilemma, from discovering the shortest route through all the rides at Disney World to finding large groups of friends on Facebook. The Golden Ticket explores what we truly can and cannot achieve computationally, describing the benefits and unexpected challenges of this compelling problem.
192 pages, Hardcover
First published January 1, 2013
67 people are currently reading
730 people want to read
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 30 of 64 reviews
May 9, 2013
There is good and bad news early on in this book about the P versus NP problem that haunts computing. The good news is that on the description I expected this to be a dull, heavy going book, and it’s not at all. Lance Fortnow makes what could be a fairly impenetrable and technical maths/computing issue light and accessible.
The bad news is that frustratingly he doesn’t actually tell you what P and NP mean for a long time, just gives rather sideways definitions of the problem along the lines of ‘P refers to the problems we can solve quickly using computers. NP refers to the problems to which we would like to find the best solution’, and also that he makes a couple of major errors early on, which make it difficult to be one hundred percent confident about the rest of the book.
The errors come in a section where he imagines a future where P=NP has been proved. This would mean you could write an algorithm to very efficiently match things and select from data. Fortnow suggests that our lives would be transformed. This is slightly cringe-making as fictional future histories often are, but the real problem is that he tells us that the algorithm would make it possible to do two things that I think just aren’t true.
First he says that from DNA you would be able to identify what a person looks like and their personality. Unfortunately, these are both strongly influenced by epigenetic/environmental issues. Anyone who knows adult identical twins (with the same basic DNA) will know that they can look quite different and certainly have very different personalities. And they will usually have been brought up in the same environment. Fortnow is forgetting one of the oldest essentials of computing – it doesn’t matter how good your algorithm is, GIGO – garbage in; garbage out.
The other, arguably worse error is that he says that it will be possible to have accurate weather forecasts going forward X days. This is so horribly wrong. He should have read my book Dice World. The reason you can’t predict the weather at all beyond about 10 days is nothing to do with the quality of the model/algorithm, it is because the system is chaotic. Firstly we just don’t know, and never can know, the initial conditions to enough decimal places not to deviate from the real world. When Lorenz first discovered chaos it was because he entered the starting values in his model to 4 decimal places rather than the 6 to which the model actually worked. It soon deviated from the previous run. We can’t measure things accurately enough. The other problem is that the weather system is so complex – hence the slightly misleading title of Lorenz’s famous paper Does the flap of a butterfly’s wings in Brazil set off a tornado in Texas? – that we can’t possible take into account enough inputs to ever have so good a model as to go forwards that far. Sorry, Lance, it ain’t going to happen.
For the rest, the first half or so of the book goes along pretty well, gradually opening up the nature of P and NP, the problems that are of interest and the ‘hardest’ NP complete problems. I found the main example, used throughout, a hypothetical world called Frenemy where everyone is either a friend or enemy of everyone else confusing and not particularly useful, but Fortnow gets plenty of good stuff in. After that it’s as if he rather runs out of material and it gets a bit repetitious or has rather tangential chapters.
Overall, despite the flaws, a much better and more readable book than I thought it was going to be – but probably best for maths/computing buffs rather than the general popular science audience.
Review first published on www.popularscience.co.uk and reproduced with permission
The bad news is that frustratingly he doesn’t actually tell you what P and NP mean for a long time, just gives rather sideways definitions of the problem along the lines of ‘P refers to the problems we can solve quickly using computers. NP refers to the problems to which we would like to find the best solution’, and also that he makes a couple of major errors early on, which make it difficult to be one hundred percent confident about the rest of the book.
The errors come in a section where he imagines a future where P=NP has been proved. This would mean you could write an algorithm to very efficiently match things and select from data. Fortnow suggests that our lives would be transformed. This is slightly cringe-making as fictional future histories often are, but the real problem is that he tells us that the algorithm would make it possible to do two things that I think just aren’t true.
First he says that from DNA you would be able to identify what a person looks like and their personality. Unfortunately, these are both strongly influenced by epigenetic/environmental issues. Anyone who knows adult identical twins (with the same basic DNA) will know that they can look quite different and certainly have very different personalities. And they will usually have been brought up in the same environment. Fortnow is forgetting one of the oldest essentials of computing – it doesn’t matter how good your algorithm is, GIGO – garbage in; garbage out.
The other, arguably worse error is that he says that it will be possible to have accurate weather forecasts going forward X days. This is so horribly wrong. He should have read my book Dice World. The reason you can’t predict the weather at all beyond about 10 days is nothing to do with the quality of the model/algorithm, it is because the system is chaotic. Firstly we just don’t know, and never can know, the initial conditions to enough decimal places not to deviate from the real world. When Lorenz first discovered chaos it was because he entered the starting values in his model to 4 decimal places rather than the 6 to which the model actually worked. It soon deviated from the previous run. We can’t measure things accurately enough. The other problem is that the weather system is so complex – hence the slightly misleading title of Lorenz’s famous paper Does the flap of a butterfly’s wings in Brazil set off a tornado in Texas? – that we can’t possible take into account enough inputs to ever have so good a model as to go forwards that far. Sorry, Lance, it ain’t going to happen.
For the rest, the first half or so of the book goes along pretty well, gradually opening up the nature of P and NP, the problems that are of interest and the ‘hardest’ NP complete problems. I found the main example, used throughout, a hypothetical world called Frenemy where everyone is either a friend or enemy of everyone else confusing and not particularly useful, but Fortnow gets plenty of good stuff in. After that it’s as if he rather runs out of material and it gets a bit repetitious or has rather tangential chapters.
Overall, despite the flaws, a much better and more readable book than I thought it was going to be – but probably best for maths/computing buffs rather than the general popular science audience.
Review first published on www.popularscience.co.uk and reproduced with permission
December 30, 2013
As a computer scientist, I was thrilled to see a book that wants to popularize the P-NP problem.
It describes a world what would happen if someone would prove that P=NP. Consequences: there are no more hard problems in the world, everything is easy, from predicting the weather accurately to healing cancer. This is utterly wrong! And for many reasons.
Worst of all, the “Golden ticket” problem from “Charlie and the Chocolate Factory” is given as an example of an NP problem, which is wrong, it is P. Seems clear to me that the author doesn’t get the P-NP problem himself.
This book is full of errors, very disappointing.
It describes a world what would happen if someone would prove that P=NP. Consequences: there are no more hard problems in the world, everything is easy, from predicting the weather accurately to healing cancer. This is utterly wrong! And for many reasons.
Worst of all, the “Golden ticket” problem from “Charlie and the Chocolate Factory” is given as an example of an NP problem, which is wrong, it is P. Seems clear to me that the author doesn’t get the P-NP problem himself.
This book is full of errors, very disappointing.
November 30, 2024
This book had been sitting on my "to read" shelf for a long while, so I finally decided to pull it down and read it. It generally does a good job of explaining a complex topic, and why people outside of the world of computer science might care. P basically describes problems that can be solved with computers in a reasonable time; NP consists of problems where we can check solutions with a computer but coming up with an optimal solution might take, effectively, an infinite amount of time. The open question is whether some unknown techniques might solve NP problems in a way that puts them in the P class. One surprising idea that the author discusses is that although learning that P=NP would dramatically increase the types of problems we could solve with computers, it might also have significant negative side effects (e.g. on computer security, job losses through automation). But it's not a big worry, because most scientists believe that P!=NP is more likely true although it hasn't been proven. At any rate, I enjoyed reading this, but also feel a little humbled, since I have a Master's degree in CS and still have trouble wrapping my head around some parts of this topic even when the discussion is geared to the layman!
May 28, 2016
Este é o primeiro livro de divulgação de ciência da computação que tive conhecimento, só por isso já merece uma nota 5 pela originalidade de criar algo que praticamente ainda não existe na área.
O livro explica o principal problema da ciência da computação e um dos problemas mais importantes da matemática: P = NP? Cerca de 85% a 90% do livro é MUITO didático e bem no estilo "divulgação da área para leigos", permitindo que qualquer pessoa entenda sobre a área e perceba o quão importante é esse problema para a computação. Nos 10% restantes (do meio para o final do livro) o autor acaba cometendo alguns deslizes na didática e deixa esses trechos um pouco complicado para leigos - o que é muito triste, dado que o restante do livro é impecável.
Uma ótima leitura para quem quer conhecer de forma bem simples um problema muito abrangente e importante na ciência da computação. Falha em alguns aspectos na didática no meio do livro, mas isso não compromete a leitura e a simplicidade do restante. Ademais, uma ótima primeira tentativa de trazer a ciência da computação para o grande público.
O livro explica o principal problema da ciência da computação e um dos problemas mais importantes da matemática: P = NP? Cerca de 85% a 90% do livro é MUITO didático e bem no estilo "divulgação da área para leigos", permitindo que qualquer pessoa entenda sobre a área e perceba o quão importante é esse problema para a computação. Nos 10% restantes (do meio para o final do livro) o autor acaba cometendo alguns deslizes na didática e deixa esses trechos um pouco complicado para leigos - o que é muito triste, dado que o restante do livro é impecável.
Uma ótima leitura para quem quer conhecer de forma bem simples um problema muito abrangente e importante na ciência da computação. Falha em alguns aspectos na didática no meio do livro, mas isso não compromete a leitura e a simplicidade do restante. Ademais, uma ótima primeira tentativa de trazer a ciência da computação para o grande público.
July 22, 2017
Everything is doing some computations. Everything in the whole universe. The computational flavours range from Math and Physics to Biology and Economics; bounded by our current science. Some computations are feasible within human timeframe (P - polynomial), some are not (NP-complete - non polynomial). For example, you can easily start a computation at home that will outlive yourself. What a messy universe! (Even light travels so slow here) The golden ticket to "paradise" is to proof that hard problems (NP) can be reduced to possible problems (P), then P = NP. Lance explores this magnificent challenge using several entertaning analogies (e.g., finding one ticket within many many chocolate bars). To conclude that, maybe, even ask if P=NP is completely nonsense but it is pushing us forward. Some of us are adventurous enough to try impossible things and civilization has been accumulating their results .
July 21, 2022
a nice controversial Amazon review
He has a chapter about what the world would be like if P=NP and it is completely ignorant and scientifically inaccurate.
He ignores roughly a century of scientific and mathematical discoveries about the limits of our knowledge. things like the Heisenberg's uncertainty principle, Godel's proof's and the theory of Chaos are all ignored. He completely misunderstands "The butterfly effect."
I am astonished that a University press of any kind published this book much lees Princeton university press. This book is fiction and sloppy beyond belief.
Steven R. Severance
He has a chapter about what the world would be like if P=NP and it is completely ignorant and scientifically inaccurate.
He ignores roughly a century of scientific and mathematical discoveries about the limits of our knowledge. things like the Heisenberg's uncertainty principle, Godel's proof's and the theory of Chaos are all ignored. He completely misunderstands "The butterfly effect."
I am astonished that a University press of any kind published this book much lees Princeton university press. This book is fiction and sloppy beyond belief.
Steven R. Severance
May 21, 2013
I really enjoyed this book. When I picked it up, I wasn't sure if I would enjoy reading a book about math for the first time since college, but I'm so glad I read it!
The author does a great job of describing classic computational problems, and how these matter to the real world. He succeeds in explaining computational complexity in a highly accessible and engaging manner. He has taken an extremely abstract subject and given it a relevant and practical context.
I just wish I could travel back in time and give this book to my undergraduate self.
The author does a great job of describing classic computational problems, and how these matter to the real world. He succeeds in explaining computational complexity in a highly accessible and engaging manner. He has taken an extremely abstract subject and given it a relevant and practical context.
I just wish I could travel back in time and give this book to my undergraduate self.
June 1, 2013
A quite comprehensive explanation of all aspects of the P vesus NP problem. Described very lucidly and in layman's terms, the book may not be attractive to an expert in computational complexity. But for the layman wanting to get a detailed explanation of the problem and it's developments so far, it's a great account.
September 12, 2015
it is the great graph theory book which is explained about various NP≠P problems.
April 9, 2024
This short book gives a decent explanation of the P vs NP problem and its significance in nontechnical terms. My understanding of it had been pretty hazy until taking a course this semester that required writing some NP-Completeness proofs, and apparently I still have a poor grasp of the extent of NP, because some of the things Fortnow says would be implied by P=NP were surprising to me:
I’d have liked more information on how these problems would be formulated such that a solution can be verified in polynomial time. I guess the first one might go something like: construct a sequence of actions which, when run in a physics simulator and rendered from a particular angle, produces a video matching the input. (Relatedly, there’s an example on page 17 about being able to immediately render a baseball game from any angle using video from several cameras.)
I’m less clear on the second one. Maybe you could view it as searching for an ML model that produces output that scores highly according to a classifier model trained on Shakespeare’s plays? ChatGPT is quick to assert that “the problem of verifying the ‘Shakespeare-ness’ of a play is in NP”—let’s take a moment to delight in its completely spontaneous use of the term “Shakespeare-ness”—but when pressed for details, it lists criteria like “linguistic features”, “thematic elements”, “character complexity”, and “plot structures” which sound hazy. I’m curious exactly what Fortnow had in mind.
Anyway, the book talks through some standard examples of NP-Complete problems like clique and vertex cover (using cutesy framing for the math-averse) and mentions some I hadn’t heard of before like “[f]inding the minimum energy state of a physical system such as interactive magnetic particles or soap bubble formation”[2]. It was also interesting to hear that Minesweeper and Tetris are both NP-Complete.
I appreciated the book’s discussion of history, covering both the Western and Russian development of the question and giving a very brief overview of some of the approaches for proving P ≠ NP that have been tried so far.
Before reading the cryptography chapter, I didn’t know that it’s possible to provide zero-knowledge proofs (i.e. evidence you can send to someone, which they can verify for themselves, to prove that there’s a solution to a particular instance of the problem, without giving them any details of the solution) for all NP-Complete problems. That’s pretty cool!
There’s a brief mention of “NC”, the class of “problems that computers can solve quickly in parallel”[3]. This statement was surprising to me so I think it’d be interesting to read more about:
[1] Lance Fortnow, The golden ticket (Princeton University Press, 2017), 6.
[2] Ibid., 48.
[3] Ibid., 157.
[4] Ibid., 157–58.
(crosspost)
Suppose we could simply describe a task and immediately have a program that provided that functionality. Feed in a movie of a human tying a knot, and immediately have the computer repeat the process with robotic hands. Give a computer the complete works of Shakespeare, and have the computer create a new “Shakespeare” play. Suppose whatever we can recognize we can find. We can if P = NP.[1]
I’d have liked more information on how these problems would be formulated such that a solution can be verified in polynomial time. I guess the first one might go something like: construct a sequence of actions which, when run in a physics simulator and rendered from a particular angle, produces a video matching the input. (Relatedly, there’s an example on page 17 about being able to immediately render a baseball game from any angle using video from several cameras.)
I’m less clear on the second one. Maybe you could view it as searching for an ML model that produces output that scores highly according to a classifier model trained on Shakespeare’s plays? ChatGPT is quick to assert that “the problem of verifying the ‘Shakespeare-ness’ of a play is in NP”—let’s take a moment to delight in its completely spontaneous use of the term “Shakespeare-ness”—but when pressed for details, it lists criteria like “linguistic features”, “thematic elements”, “character complexity”, and “plot structures” which sound hazy. I’m curious exactly what Fortnow had in mind.
Anyway, the book talks through some standard examples of NP-Complete problems like clique and vertex cover (using cutesy framing for the math-averse) and mentions some I hadn’t heard of before like “[f]inding the minimum energy state of a physical system such as interactive magnetic particles or soap bubble formation”[2]. It was also interesting to hear that Minesweeper and Tetris are both NP-Complete.
I appreciated the book’s discussion of history, covering both the Western and Russian development of the question and giving a very brief overview of some of the approaches for proving P ≠ NP that have been tried so far.
Before reading the cryptography chapter, I didn’t know that it’s possible to provide zero-knowledge proofs (i.e. evidence you can send to someone, which they can verify for themselves, to prove that there’s a solution to a particular instance of the problem, without giving them any details of the solution) for all NP-Complete problems. That’s pretty cool!
There’s a brief mention of “NC”, the class of “problems that computers can solve quickly in parallel”[3]. This statement was surprising to me so I think it’d be interesting to read more about:
…we don’t even know if NP = NC. NP = NC means every NP search problem can be solved extremely quickly on systems with many computers and/or cores, an even more beautiful world than that of P = NP.[4]
[1] Lance Fortnow, The golden ticket (Princeton University Press, 2017), 6.
[2] Ibid., 48.
[3] Ibid., 157.
[4] Ibid., 157–58.
(crosspost)
April 10, 2020
Lance Fortnow's book, The Golden Ticket: P, NP, and the Search for the Impossible takes non-technical readers on a fabulous journey through computer science's most prolific open question: "is P equal to NP?". It's a question regarding the limits of computability: is there a class of problems for which efficient algorithms do not exist? Many of the world's hardest problems (e.g. protein folding, schedule optimization, etc...) are technically solvable but require an intractable amount of compute resources. To be more specific, it would take the world's most powerful super computer trillions of years to calculate an answer. There are literally thousands of problems like this. What's interesting is that the majority of these intractable problems are equivalent from a computing perspective. That is to say, discovery of an efficient algorithm for any one of the problems essentially solves them all. The concept is profound to say the least. Unfortunately, almost all reputable computer scientist believe that P is NOT equal to NP and therefore such an algorithm will always remain beyond our grasp. However, they haven't been able to prove this to be true.
Mr. Fortnow does an excellent job of capturing the spirit of the complexity classes P and NP while avoiding the mathematical technicalities. The prose is delightfully written and easy to consume. He blends historic context, fictional scenarios, and technical explanation into an engaging narrative. The only criticism is the omission of many salient details as it barely scratches the surface of the subject. However, this objection is not reflected in the overall rating owing to the fact that target audience most likely does not need this level of detail.
In conclusion, The Golden Ticket is a great resource for anyone wishing to obtain a visceral conception of the P, NP problem without wading through technicalities. It's an engaging and quick read that serves as base introduction to the topic. Computer scientist will be better served by alternate material.
Mr. Fortnow does an excellent job of capturing the spirit of the complexity classes P and NP while avoiding the mathematical technicalities. The prose is delightfully written and easy to consume. He blends historic context, fictional scenarios, and technical explanation into an engaging narrative. The only criticism is the omission of many salient details as it barely scratches the surface of the subject. However, this objection is not reflected in the overall rating owing to the fact that target audience most likely does not need this level of detail.
In conclusion, The Golden Ticket is a great resource for anyone wishing to obtain a visceral conception of the P, NP problem without wading through technicalities. It's an engaging and quick read that serves as base introduction to the topic. Computer scientist will be better served by alternate material.
February 10, 2022
I went into it with two expectation: First, to thoroughly learn what the hell the terms "P" and "NP" actually mean. This is very unfortunate since the author went to great lengths to avoid answering this very question.
Shockingly, Wikipedia (which is infamous for layman-inscrutable entries for computer science and mathematics topics) has a better summary:
For that, I might have saved myself a lot of pain and skipped the book.
The second thing I wanted fro this book was a history of the P vs NP problem that was both interesting and would help me understand what problems were being solved at the time (if any). And I'm sad to say that this falls very short of an interesting historical account as well.
Instead, it feels like what it is: a small essay blown up into a book with expanded examples and quite a lot of prose that doesn't contribute to insight or understanding.
I did enjoy parts of this - particularly the last third or so, but since it missed the mark (I'd set for it) by such a wide margin, all I can feel is disappointment.
Shockingly, Wikipedia (which is infamous for layman-inscrutable entries for computer science and mathematics topics) has a better summary:
An answer to the P versus NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If it turns out that P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.
For that, I might have saved myself a lot of pain and skipped the book.
The second thing I wanted fro this book was a history of the P vs NP problem that was both interesting and would help me understand what problems were being solved at the time (if any). And I'm sad to say that this falls very short of an interesting historical account as well.
Instead, it feels like what it is: a small essay blown up into a book with expanded examples and quite a lot of prose that doesn't contribute to insight or understanding.
I did enjoy parts of this - particularly the last third or so, but since it missed the mark (I'd set for it) by such a wide margin, all I can feel is disappointment.
April 28, 2020
The Golden Ticket is a readily accessible account of the well-known P=NP problem. It will be of interest to anyone wanting to learn more about this problem and its importance to mathematics and computer science.
The P versus NP problem has been around for a few decades and is important enough to be contained in the Millenium Prize Problems conceived at the start of the 21st century. It continues to fascinate and excite many researchers in the academic community.
The book is a fascinating account of the problem's history, the revolution it would spark should it be proven to be correct and direction of current and future research. The prose is straightforward with plenty of examples and minimum mathematics. The real-world descriptions of NP problems help keep the reader's interest.
The Golden Ticket isn't a textbook so don't read this book if you want to learn the detailed mechanics of P, NP and NP-Complete problems. It's more a general-interest book and a short-read at that. As such, I highly recommend it for those people interested in learning more about the P versus NP problem and its importance to society.
The P versus NP problem has been around for a few decades and is important enough to be contained in the Millenium Prize Problems conceived at the start of the 21st century. It continues to fascinate and excite many researchers in the academic community.
The book is a fascinating account of the problem's history, the revolution it would spark should it be proven to be correct and direction of current and future research. The prose is straightforward with plenty of examples and minimum mathematics. The real-world descriptions of NP problems help keep the reader's interest.
The Golden Ticket isn't a textbook so don't read this book if you want to learn the detailed mechanics of P, NP and NP-Complete problems. It's more a general-interest book and a short-read at that. As such, I highly recommend it for those people interested in learning more about the P versus NP problem and its importance to society.
April 21, 2022
I was really looking forward to this, but it's so poorly written I stopped less than halfway through. Where did I stop? When it started talking about what a computer is. Seriously. It's written not just for the layman but also doesn't even explain concepts well. And it jumps to a new topic with seemingly no warning. Oh, well, maybe there's another book on this topic worth reading.
(For what it's worth, I can handle the math, but was open to either a philosophical or mathematical discussion of P and NP.)
(For what it's worth, I can handle the math, but was open to either a philosophical or mathematical discussion of P and NP.)
April 26, 2018
Reasonably entertaining and does have some useful information about P vs NP (enough to convince people that you know what it is), but it doesn’t really tell you exactly what P vs NP is, which I suppose is fair. But I think the nontechnical example at the core of the book, finding ‘cliques’ in a friendship network, is really not a great example and is quite hard to follow.
The chapters on cryptography, while interesting, seem to be really out of place.
The chapters on cryptography, while interesting, seem to be really out of place.
April 29, 2022
Ha sido muy interesante descubrir los "límites" de la computación y además de forma muy pedagógica. Recomendable para alguien con CERO conocimiento de computación, aunque en ocasiones es difícil seguir los procesos lógicos. Me ha encantado la forma de describir la cuántica!
May 12, 2017
Lance Fortnow, has explained the concepts of what is P and NP in this book like a novel. If you watched the film Charlie and the Chocolate Factory; you will enjoy reading this book.
November 18, 2017
A nice introduction to p-np, np-completeness, cryptography & even quantum computing.
July 2, 2018
A really good intro to the P/NP problem. Probably not that accessible to non-CS folks, but a very good overview.
June 8, 2020
I still don't really get it though
April 13, 2022
A great introduction, without any mathematics or formal logic, to the P/NP problem and its importance.
November 3, 2022
Many beautiful challenges waiting to be explored.
November 30, 2024
Well-researched and well-written, Fortnow's book is a great addition to the popular computer science genre. Some of it is tough going, but ultimately rewarding.
December 30, 2016
This book is an attempt at a "popular" (non-technical) explanation of the P-vs-NP problem.
Fortnow doesn't even give a rigorous definition of the problem - which is fine, because a rough one is good enough for the purposes of the book. Plus, you halve your audience with every mathematical formula included in a book. (Source: apocryphal; I read it once somewhere, attributed to some publisher or other.)
I came in with a basic understanding of the problem. I don't think I came to any new insights. And I really don't think that someone who had never heard of P-vs-NP before would walk away with more than the very vaguest of notions.
Still, there were quite a few interesting details, metaphors, etc.
And it was a surprising quick read.
Fortnow doesn't even give a rigorous definition of the problem - which is fine, because a rough one is good enough for the purposes of the book. Plus, you halve your audience with every mathematical formula included in a book. (Source: apocryphal; I read it once somewhere, attributed to some publisher or other.)
I came in with a basic understanding of the problem. I don't think I came to any new insights. And I really don't think that someone who had never heard of P-vs-NP before would walk away with more than the very vaguest of notions.
Still, there were quite a few interesting details, metaphors, etc.
And it was a surprising quick read.
March 18, 2017
well-written overview of the P = (or <>) NP problem. good summary of the core of the issue and interesting discussion of the impacts. the section on cryptography is my favourite. some of the ideas (e.g. fully homomorphic encryption schemes) are industry-changers.
January 30, 2018
Very broadly speaking, there are two kinds of math problems in the world: Ones which can easily be solved by a computer and one whose solutions can be easily checked by a computer. "Solved" in this sense means "proven to be true for any value of the variable." Checked means that if a number is plugged into the equation, it can be seen if the equation still makes sense or if it produces an impossible answer.
The set of solvable equations is called P. The set of checkable equations is called NP. And one of the biggest questions in mathematics, one whose solution could make the world a completely different place, is does P = NP? Georgia Tech Computer Science professor Lance Fortnow has spent much of his career considering this problem and writes about some of the history of its investigation in 2013's The Golden Ticket: P, NP and the Search for the Impossible.
Current mathematical thought suggests that P ≠ NP, although it can't yet prove that to be true. Fortnow outlines what kind of solutions to world problems might happen if P = NP, such as a wide range of cures for cancer not now possible. It would also make some things significantly more difficult, such as online security. Current online security relies on equations that can't be easily solved because of the number of digits they use and immense number of possible number combinations. But in a P = NP world, those equations could be solved and so computer security would become much more complicated.
Fortnow also describes some of the history of different attempts to determine whether we live in a world where P = NP or where P ≠ NP. He offers some thoughts on what the development of quantum computing, which is projected to be immensely faster than current computing, might mean about getting a definitive answer either way. He keeps the formula and equation use to a minimum, saving much of it for appendices for the readers interested in that part of the story.
The Golden Ticket is a great introduction to a math problem that few people know about and even fewer understand, and a good way to try to start thinking about it and its implications. Although Fortnow doesn't delve much into the philosophical implications of the P, NP problem, he provides enough of the basic tools for the curious to begin that part of the journey themselves.
Original available here.
The set of solvable equations is called P. The set of checkable equations is called NP. And one of the biggest questions in mathematics, one whose solution could make the world a completely different place, is does P = NP? Georgia Tech Computer Science professor Lance Fortnow has spent much of his career considering this problem and writes about some of the history of its investigation in 2013's The Golden Ticket: P, NP and the Search for the Impossible.
Current mathematical thought suggests that P ≠ NP, although it can't yet prove that to be true. Fortnow outlines what kind of solutions to world problems might happen if P = NP, such as a wide range of cures for cancer not now possible. It would also make some things significantly more difficult, such as online security. Current online security relies on equations that can't be easily solved because of the number of digits they use and immense number of possible number combinations. But in a P = NP world, those equations could be solved and so computer security would become much more complicated.
Fortnow also describes some of the history of different attempts to determine whether we live in a world where P = NP or where P ≠ NP. He offers some thoughts on what the development of quantum computing, which is projected to be immensely faster than current computing, might mean about getting a definitive answer either way. He keeps the formula and equation use to a minimum, saving much of it for appendices for the readers interested in that part of the story.
The Golden Ticket is a great introduction to a math problem that few people know about and even fewer understand, and a good way to try to start thinking about it and its implications. Although Fortnow doesn't delve much into the philosophical implications of the P, NP problem, he provides enough of the basic tools for the curious to begin that part of the journey themselves.
Original available here.
July 7, 2014
I came to this book with no prior knowledge of the P/NP problem and after reading I have only the slightest surface level knowledge of the topic. As I was reading, I frequently had to look things up (including the definitions of P, NP, and NP-complete) in order to understand what the author was getting at.
I did not like the frequent use of made up scenarios to illustrate what the author was attempting to explain. I would have preferred examples of actual situations to illustrate how the P/NP problem manifests in the real world, how it impacts us, and why it matters. I would expect that an experienced science communicator with a deep understanding of the topic could have provided more realistic situations then a make-believe world called Frenemy.
The writing was not always clear enough for me to follow the author's train of thought to a conclusion. He would be talking about something and then all the sudden talking about something else which may or may not have been connected, but I couldn't figure it out.
I was very interested in this topic and really wanted a more in depth understanding of it. I did not get that from this book. As previously stated, this book was my first introduction to the P/NP problem and I was excited to learn more about it, but this book was not the vehicle for doing so. I only finished reading it so that I could discuss with my book group.
I did not like the frequent use of made up scenarios to illustrate what the author was attempting to explain. I would have preferred examples of actual situations to illustrate how the P/NP problem manifests in the real world, how it impacts us, and why it matters. I would expect that an experienced science communicator with a deep understanding of the topic could have provided more realistic situations then a make-believe world called Frenemy.
The writing was not always clear enough for me to follow the author's train of thought to a conclusion. He would be talking about something and then all the sudden talking about something else which may or may not have been connected, but I couldn't figure it out.
I was very interested in this topic and really wanted a more in depth understanding of it. I did not get that from this book. As previously stated, this book was my first introduction to the P/NP problem and I was excited to learn more about it, but this book was not the vehicle for doing so. I only finished reading it so that I could discuss with my book group.
July 16, 2013
Computer Science doesn't have a lot of great pop science writers. The issues are abstractions of abstractions of abstractions, and the jargon is sometimes difficult, even when the issues are pretty simple.
P = NP? is the shorthand for an outstanding research question in Computer Science. It is a question about what problems are inherently hard to compute.
It turns out that on the hook of P=NP? there hangs a number of great stories and anecdotes, some current and some going back to the foundation era of CS during the cold war.
Lance Fortnow is a Computer Science prof at Georgia Tech, and his writing style is a real pleasure. I think most of my teenaged students who basically are somewhat interested in computing would get through this and enjoy it. (Full diclosure: I am a high school CS teacher.) How he manages to expunge professorisms from his writing so well I have no idea.
He tells stories about the present and historic researchers and speculative stories about what a world where NP-hard problems could be solved in polynomial time.
If you liked "A Brief History of Time" or other science writing for (intelligent) lay audiences this might grab you. If you are a CS student of any stripe you should also take a look.
P = NP? is the shorthand for an outstanding research question in Computer Science. It is a question about what problems are inherently hard to compute.
It turns out that on the hook of P=NP? there hangs a number of great stories and anecdotes, some current and some going back to the foundation era of CS during the cold war.
Lance Fortnow is a Computer Science prof at Georgia Tech, and his writing style is a real pleasure. I think most of my teenaged students who basically are somewhat interested in computing would get through this and enjoy it. (Full diclosure: I am a high school CS teacher.) How he manages to expunge professorisms from his writing so well I have no idea.
He tells stories about the present and historic researchers and speculative stories about what a world where NP-hard problems could be solved in polynomial time.
If you liked "A Brief History of Time" or other science writing for (intelligent) lay audiences this might grab you. If you are a CS student of any stripe you should also take a look.
January 26, 2014
Finished the book in half a day. Problem with The Golden Ticket is that it tries to remain non-technical about a topic, which is very technical. As expected, it does not succeed, and has to go into some details later, which defies the purpose of not giving definitions of P and NP anyway.
Being a CS student, i feel that defining P and NP (the way the author does later, easily solvable and easily verifiable) in first few chapters would have been a better idea. A naive reader might feel a bit irritated by tiptoeing around the actual definitions. Still, the book picks up some pace after the author is done with his description of the imaginary world where P=NP. Many things in the imaginary world make in ask "what? how is that possible if P=NP?", an no explanation is provided for the same.
But as i said, the book does a reasonably good job after that for a novice reader to introduce him to the problem. The examples are good, the big numbers are a bit too many, and placeholders could be used. Last chapters are more about future of computing than about P and NP, but are interesting.
It is like a popular science article for someone who already knows about the problem, and a nice introductory book for others.
Being a CS student, i feel that defining P and NP (the way the author does later, easily solvable and easily verifiable) in first few chapters would have been a better idea. A naive reader might feel a bit irritated by tiptoeing around the actual definitions. Still, the book picks up some pace after the author is done with his description of the imaginary world where P=NP. Many things in the imaginary world make in ask "what? how is that possible if P=NP?", an no explanation is provided for the same.
But as i said, the book does a reasonably good job after that for a novice reader to introduce him to the problem. The examples are good, the big numbers are a bit too many, and placeholders could be used. Last chapters are more about future of computing than about P and NP, but are interesting.
It is like a popular science article for someone who already knows about the problem, and a nice introductory book for others.
January 16, 2014
Meh. The first half of the book was neat. The author discusses what the world would be like of P=NP. In this world, almost all of the technology we could ever imagine is possible, and computers can do incredible things for good and evil.
I kept waiting for the part where he would discuss complexity theory so that I could come away from the book knowing a little about it. No such luck, however. The concepts are discussed at an extremely abstracted level. The problems the author did discuss did not have good explanations, especially considering his aim for a general audience. I did not follow many of his arguments about "obvious" heuristics for several problems. The entire last chapter is about the future of computing, and had nothing to do with complexity theory. Still, there was good coverage of the history of the problem in the East and the West (East meaning USSR). There were some interesting bits about the characters behind the theories, but overall this was not a compelling read like, say, Fermat's Enigma or Music of the Primes. Very disappointing.
It was, however, a very fast read.
I kept waiting for the part where he would discuss complexity theory so that I could come away from the book knowing a little about it. No such luck, however. The concepts are discussed at an extremely abstracted level. The problems the author did discuss did not have good explanations, especially considering his aim for a general audience. I did not follow many of his arguments about "obvious" heuristics for several problems. The entire last chapter is about the future of computing, and had nothing to do with complexity theory. Still, there was good coverage of the history of the problem in the East and the West (East meaning USSR). There were some interesting bits about the characters behind the theories, but overall this was not a compelling read like, say, Fermat's Enigma or Music of the Primes. Very disappointing.
It was, however, a very fast read.
Displaying 1 - 30 of 64 reviews