The Golden Ticket: P, NP, and the Search for the Impossibleby Lance Fortnow
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/i>
Most Helpful Customer Reviews
See all customer reviews
In The Golden Ticket, Lance Fortnow takes a fascinating look at a conundrum that has been around since Kurt Gödel wrote about it in a letter to a pioneer in the field of computer science, John von Neumann in 1956. The mystery? Is P = NP? Gödel didn’t get credit for the question because the letter didn’t come to public light for years, and in the meantime Sam Cook in the West and Leonid Levin in the East each posed the question to their respective mathematical communities and in fact, Sam Cook received the Turing Award for his work on the subject. Fortnow explores what he calls “the beautiful world” that we would live in if we could actually achieve P = NP where P represents problems that can be solved quickly on computers and NP represents those that cannot be solved quickly or easily. He goes through a number of problems that are satisfyingly illustrative of the complexity of the mystery: clique and map coloring to name a few. In The Golden Ticket, Fortnow, who is a professor and chair of the School of Computer Science at the Georgia Institute of Technology, writes really well. He somehow explains these problems and the enormous challenge involved (in moving from a world where P ≠ NP to the “beautiful” world where P = NP) in language and illustrations which make it easy for the non-technical among us to easily comprehend. And in doing this, he creates a timeline of mathematical history that starts the 9th century mathematician whose nane in Latin (Algoriti) gave us the name algorithms for the computational procedures, to the relative present and IBM’s Charles Bennett et al, and their research into quantum teleportation. P = NP or P ≠ NP is an captivating conundrum and The Golden Ticket makes it available to the layman in an enjoyable, easy-to-read style that returns a lot for the investment one makes in the reading of it.