20 books
—
13 voters

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

by

**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 ...more

## Get A Copy

Hardcover, 176 pages

Published
March 31st 2013
by Princeton University Press
(first published January 1st 2013)

## 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

Start your review of The Golden Ticket: P, Np, and the Search for the Impossible

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

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

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 ...more

The chapters on cryptography, while interesting, seem to be really out of place.

A nice introduction to p-np, np-completeness, cryptography & even quantum computing.
...more

I still don't really get it though

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

The set of solvable equations is called P. The set of checkable equations is called NP. An ...more

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

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

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

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

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

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

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

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

There are no discussion topics on this book yet.
Be the first to start one »

## Goodreads is hiring!

## 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

No trivia or quizzes yet. Add some now »

“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…