Goodreads helps you keep track of books you want to read.
Start by marking “The Golden Ticket: P, Np, and the Search for the Impossible” as Want to Read:
The Golden Ticket: P, Np, and the Search for the Impossible
Enlarge cover
Rate this book
Clear rating
Open Preview

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

3.60  ·  Rating details ·  417 ratings  ·  58 reviews
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
Hardcover, 176 pages
Published March 31st 2013 by Princeton University Press (first published January 1st 2013)
More Details... Edit Details

Friend Reviews

To see what your friends thought of this book, please sign up.

Reader Q&A

To ask other readers questions about The Golden Ticket, please sign up.

Be the first to ask a question about The Golden Ticket

Community Reviews

Showing 1-30
Average rating 3.60  · 
Rating details
 ·  417 ratings  ·  58 reviews

More filters
Sort order
Start your review of The Golden Ticket: P, Np, and the Search for the Impossible
Brian Clegg
May 09, 2013 rated it liked it
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
Peter (Pete) Mcloughlin
Does P=NP? This problem is one of the most important problems that remains unsolved in computer science and mathematics. If it is solved and the solution of P=NP is true it will be the greatest discovery of the 21st century. P stands for Polynomial time. Computer problems that can be solved in Polynomial time are tractable and can be solved in a reasonable time. NP stands for NonPolynomial time currently NP problems are intractable and can not be solved in a reasonable time. If P=NP then we sho ...more
Roberto Rigolin F Lopes
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 pr ...more
May 16, 2013 rated it really liked it
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
Debasish Ghosh
Jun 01, 2013 rated it really liked it
Shelves: dg-book-shelf
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.
Ami Iida
Sep 04, 2015 rated it really liked it
Shelves: math
it is the great graph theory book which is explained about various NP≠P problems.
Dale Alleshouse
Apr 04, 2020 rated it it was amazing  ·  review of another edition
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 r ...more
Apr 28, 2020 rated it really liked it
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 o
Robert Martin
Apr 26, 2018 rated it liked it
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.
Akarsh Seggemu
May 12, 2017 rated it really liked it
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.
Nov 18, 2017 rated it liked it
A nice introduction to p-np, np-completeness, cryptography & even quantum computing. ...more
Dana Robinson
Jul 02, 2018 rated it it was amazing
A really good intro to the P/NP problem. Probably not that accessible to non-CS folks, but a very good overview.
Isabelle Leo
I still don't really get it though
Edward B.
Dec 22, 2016 rated it liked it
Shelves: comp-sci
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. An
Roger B
Mar 18, 2017 rated it really liked it
Shelves: math
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. ...more
Brett T
Oct 18, 2017 rated it really liked it
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. An
Patrick Stein
May 19, 2013 rated it liked it
Shelves: math
Some initial annoyance:

Added: 2013-05-22

I finished this book last night. The book has some interesting discussion of different NP problems. And some brief naming of key figures in developing the field. However, the book was really short and yet there is still lots of it that had no place.

There is a big discussion of Quantum Computing at the end. QC is interesting and all. But, the discussion starts by saying we already know that QC won't be able to do NP-
Jul 07, 2014 rated it it was ok  ·  review of another edition
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 pr
Freeman Crouch
Jul 16, 2013 rated it really liked it
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
Ashutosh Rai
Jan 26, 2014 rated it liked it
Shelves: science, non-fiction
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 irrita
Nathan Glenn
Jan 04, 2014 rated it liked it
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
May 16, 2013 rated it liked it
Shelves: math-and-science
Here is a great introduction to the P vs. NP problem in mathematics. It deals with whether or not complex problems can be solved efficiently. In short, we do not know whether P = NP. Brilliant computing theorists and mathematicians have worked with the problem ever since Alan Turing invented the modern concept of computing. If P = NP, we live in a world where seemingly impossible, large scale problems can quickly be checked for solutions. Since this does not generally ring true with the nature o ...more
Stephen Davis
Jul 04, 2015 rated it really liked it
Shelves: general
The Golden Ticket introduces the limitation of computers, and how not all problems to solve are created equally. Some problems are easy like counting from one to ten. While others take a bit longer to solve like sorting all the people in the phone book alphabetically. And others take so long that finding an approximation to a good solution is something we can accept over spending years to find the perfect answer. If it turns out that relatively easy problem solutions can be used to solve really ...more
Swamy Atul
Jun 20, 2013 rated it really liked it
This is science fiction for those who love math! It takes us into a world where every problem has a precise, uncontested solution. It's a wonderful world.
I think NP problems are evolutionary, much like any other stream of science. The degree of difficulty in overcoming a problem has always been limited by our wisdom and the tools at our disposal. When we can not solve a problem, we attribute it to Gods, demons and the flying spaghetti monster. Our ancestors saw the sun, it blinded their eyes, an
Oliver Sampson
May 10, 2016 rated it liked it
Writing a Popular Science book is tough work. Very few authors seem to be able to walk the line between too technical for the layperson and technical enough to keep the more advanced reader interested. (James Gleick and Simon Singh seem to do this effortlessly.) Put on top of that the tackling a topic as abstract as P =/!= NP and the task is formidable indeed. Mr. Fortnow tries very hard to make it accessible, but errs a little too far on the side of simplifying things for the layperson without ...more
Robert Dormer
Nov 23, 2013 rated it really liked it
Some of the explanations in the beginning are imprecise, and the second chapter dramatically overstates the practical implications of a polynomial time solution to the NP complete problems. That said, the book picks up after this, and launches into an excellent explanation of the P vs NP problem, it's history and background, and the wider implications of a solution. The examples of NP problems struck a good balance between general, easily understandable analogies and more substantial technical e ...more
Dec 30, 2013 rated it did not like it
Shelves: stopped
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.
May 27, 2013 rated it it was ok
A short book that felt long. And I have a degree in maths and write software for a living. The problem is that (IMHO) Fortnow does not have a gift for science writing, nor for making the complex understandable. Poor shifts between fictional scenarios and non-fictional bits did not help; a few times I found myself wondering whether he was describing something real, or setting up an example. Finished the book feeling not particularly more informed on P vs. NP (beyond being informed that a proof fo ...more
Pratik Tale
Feb 01, 2014 rated it liked it
This is nice introduction to the topic for general audience. It also serve as good motivation for CS major students who doing the courses in this field. As graduate student, it helps me to talk about my research outside academia.

But the chapter on the world P = NP seems far fetched from where I stand.

P.S. -- Lance Fortnow is accomplished researcher in this field and one of the very few people who can talk with authority with P = NP. So my remarks 'N = NP being far fetched' might very well be wro
Sep 22, 2015 rated it it was amazing
I read this book when it initially came out and loved it, and even more love what Dr. Fortnow is doing with this book. For so long math and computer science concepts have been seen as academic talk that should never make its way to the dinner table. But this book extends the conversation outside of the classroom by asking you to imagine a world AFTER the question of P ?=? NP is resolved. He addresses several areas where this could have an immediate impact and gives light to some of the interesti ...more
« previous 1 next »
There are no discussion topics on this book yet. Be the first to start one »

Readers also enjoyed

  • The Language of Cities
  • The Clockwork Rocket (Orthogonal, #1)
  • Salvation Lost (Salvation Sequence #2)
  • A Common-Sense Guide to Data Structures and Algorithms: Level Up Your Core Programming Skills
  • Mathematics: A Very Short Introduction
  • Alan Turing: The Enigma
  • The Art of Learning: A Journey in the Pursuit of Excellence
  • Little Eyes
  • Docker Networking and Service Discovery
  • How to Hack Computers: how to hack computers, hacking for beginners, penetration testing, hacking for dummies, computer security, computer hacking, hacking techniques, network scanning
  • Sherlock Holmes: The Complete Novels and Stories, Volume II
  • Docker in Action
  • Jytte fra Marketing er desværre gået for i dag: Sådan bruger du adfærdsdesign til at skabe forandringer i den virkelige verden
  • Jytte vender tilbage: Den umoderne guide til at skabe forandringer imod alle odds
  • The Man Who Knew The Way to the Moon
  • Boys: What It Means to Become a Man in the 21st Century
  • How Starbucks Saved My Life: A Son of Privilege Learns to Live Like Everyone Else
See similar books…

Goodreads is hiring!

If you like books and love to build cool products, we may be looking for you.
Learn more »

News & Interviews

Need another excuse to treat yourself to a new book this week? We've got you covered with the buzziest new releases of the day. To create our...
32 likes · 16 comments
“Suppose whatever we can recognize we can find. We can if P=NP.” 8 likes
“Diffie and Hellman suggested such a system, but their protocol is not as commonly used as a scheme discovered by three computer scientists, Ronald Rivest, Adi Shamir, and Leonard Adleman, in 1978 and named “RSA” after them.” 0 likes
More quotes…