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

Lance Fortnow. Princeton Univ., $26.95 (176p) ISBN 978-0-691-15649-1
This awkward but eager work introduces readers to one of the most complicated problems in mathematics. P-type problems have a single solution and can be solved easily by computer, whereas NP, or “nondeterministic polynomial” problems, involve finding the relative “best” of numerous possible answers. NP problems include map-coloring puzzles, traveling-salesman puzzles (which seek to find the best combinations of routes between locations), and clique problems, like finding the largest group of people on Facebook who are all friends of each other. Fortnow’s “Golden Ticket” would be proof that P=NP, the discovery of efficient ways to solve NP-type problems. Whoever solves this decidedly nontrivial problem—one of the Clay Institute for Mathematics’ six unsolved “Millennium Problems”—will receive a $1 million prize. In addition to exploring the actual quandary, Fortnow, chair of the Georgia Institute of Technology’s school of computer science, lays out a quick modern history of mathematical problem solving, and enthuses over the possibilities of a “beautiful world” where P=NP: the ability to quickly sequence DNA, cure cancer and AIDs, and predict the weather. Despite moments of notational confusion—what exactly do “P H NP,” “P W NP,” and “P M NP” mean?—Fortnow effectively initiates readers into the seductive mystery and importance of P and NP problems. 41 halftones, 41 line illus. (Apr.)
Reviewed on: 01/28/2013
Release date: 03/01/2013
Show other formats
Open Ebook - 1 pages - 978-1-299-15656-2
Open Ebook - 192 pages - 978-1-4008-4661-0
Stay ahead with
Tip Sheet!
Free newsletter: the hottest new books, features and more
Only $18.95/month for Digital Access
or $20.95 for Print+Digital Access!
Only $18.95/month for Digital Access
or $20.95 for Print+Digital Access!
Email Address


Log In Lost Password

PW has integrated its print and digital subscriptions, offering exciting new benefits to subscribers, who are now entitled to both the print edition and the digital editions of PW (online or via our app). For instructions on how to set up your accout for digital access, click here. For more information, click here.

The part of the site you are trying to access is now available to subscribers only. Subscribers: to set up your digital subscription with the new system (if you have not done so already), click here. To subscribe, click here.

Email with questions.

Not Registered? Click here.