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.58  ·  Rating details ·  334 Ratings  ·  57 Reviews
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 ...more
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)
Rating details
Sort: Default
|
Filter
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
...more
Caique Marques
Mar 02, 2016 rated it it was amazing
Delicioso.

The Golden Ticket é um livro para qualquer um que esteja interessado em entender um dos principais problemas enfrentados atualmente pela computação, matemática e outras ciências: a questão do P versus NP. Mesmo sendo citado bastante em meios científicos, o autor consegue mostrar que o problema P vs. NP está até nas coisas mais normais do dia-a-dia (por exemplo, como conseguir aproveitar todas as atrações dos Parques Disney em um dado intervalo de tempo?).

O ponto alto do livro é a forma
...more
Fernando Paladini
Mar 02, 2016 rated it it was amazing
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 pro
...more
Peter 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
Suni
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
...more
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.
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.
Arquero
Nov 18, 2017 rated it liked it
A nice introduction to p-np, np-completeness, cryptography & even quantum computing.
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.
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.
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
...more
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.
Brett Thomasson
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
...more
Patrick Stein
May 19, 2013 rated it liked it
Shelves: math
Some initial annoyance: http://patrickwonders.livejournal.com...

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-
...more
Tracey
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
...more
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
...more
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
...more
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
...more
Remo
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, ...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
Matt
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
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
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
...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
Bram
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.
...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
...more
Charles
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
JDK1962
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
Tim
Jul 07, 2013 rated it liked it
Short but an occasional struggle to get through at times. For computer scientists, there is nothing really new here. It is a fair review of the P = NP question. The examples and explantations are hit and miss. For the non-CS person, I am not sure why you would want to read about the P = NP question anyway.
« previous 1 3 4 5 6 7 8 9 10 11 12 next »
There are no discussion topics on this book yet. Be the first to start one »
  • Mathematical Mysteries: The Beauty and Magic of Numbers
  • The Irrationals - A Story of the Numbers You Can′t Count On
  • The Numbers Game: The Commonsense Guide to Understanding Numbers in the News, in Politics, and in Life
  • The Mathematical Universe: An Alphabetical Journey Through the Great Proofs, Problems, and Personalities
  • Poincare's Prize: The Hundred-Year Quest to Solve One of Math's Greatest Puzzles
  • In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation
  • Euler's Gem: The Polyhedron Formula and the Birth of Topology
  • Feynman Lectures On Computation
  • The Recursive Universe: Cosmic Complexity and the Limits of Scientific Knowledge
  • The Computational Beauty of Nature: Computer Explorations of Fractals, Chaos, Complex Systems, and Adaptation
  • Strange New Worlds: The Search for Alien Planets and Life Beyond Our Solar System
  • Quantum Computing Since Democritus
  • The Principles of Mathematics
  • The Complete Idiot's Guide to Game Theory
  • Weird Life: The Search for Life That Is Very, Very Different from Our Own
  • Math on Trial: How Numbers Get Used and Abused in the Courtroom
  • Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers
  • The Universe and the Teacup: The Mathematics of Truth and Beauty

Goodreads is hiring!

If you like books and love to build cool products, we may be looking for you.
Learn more »
“Suppose whatever we can recognize we can find. We can if P=NP.” 7 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…