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 computers and beyond. Lance Fortnow traces the history and development of P-NP, giving examples from a variety of disciplines, including economics, physics, and biology. He explores problems that capture the full difficulty of the P-NP dilemma, from discovering the shortest route through all the rides at Disney World to finding large groups of friends on Facebook. The Golden Ticket explores what we truly can and cannot achieve computationally, describing the benefits and unexpected challenges of this compelling problem.
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.