- Home
- The Golden Ticket

# The Golden Ticket

P, NP, and the Search for the Impossible

**Lance Fortnow **

- Hardcover2013Hardcover26.9521.95ISBN9780691156491192 pp.6 x 9 1/441 halftones. 41 line illus.Live
- Paperback2017Paperback17.9514.95ISBN9780691175782192 pp.6 x 9 1/441 halftones. 41 line illus.Live

- E-bookISBN9781400846610

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.

*Lance Fortnow*is professor and chair of the School of Computer Science at Georgia Institute of Technology and the founder and coauthor of the Computational Complexity blog.

## More about this book

- One of Amazon.com’s 2013 Best Science Books
- One of
*Choice*'s Outstanding Academic Titles for 2013 - Honorable Mention for the 2013 PROSE Award in Popular Science & Mathematics, Association of American Publishers

## Reviews

**--Alexander Nazaryan,**

*New Yorker***--**

*Publishers Weekly***--Veit Elser,**

*Science***--J.J.S. Boyce,**

*Library Journal***--**

*Booklist**The Golden Ticket*, Lance Fortnow cleverly sidesteps the issue with a boiled-down version. P is the collection of problems we can solve quickly, NP is the collection of problems we would like to solve. If P = NP, computers can answer all the questions we pose and our world is changed forever. It is an oversimplification, but Fortnow, a computer scientist at Georgia Institute of Technology, Atlanta, knows his stuff and aptly illustrates why NP problems are so important."

**--Jacob Aron,**

*New Scientist***--Rob Hardy,**

*Commercial Dispatch***--Scott Aaronson,**

*Shtetl-Optimized blog**The Golden Ticket*] is a book on a technical subject aimed at a general audience. . . . Lance's mix of technical accuracy with evocative story telling works."

**--Michael Trick,**

*Michael Trick's Operations Research Blog***--**

*Daniel Lemire's Blog***--Andrew Binstock,**

*Dr. Dobb's**The Golden Ticket*is an extremely accessible and enjoyable treatment of the most important question of theoretical computer science, namely whether P is equal to NP."

**--**

*Choice***--Michael Trick,**

*INFORMS Journal of Computing**The Golden Ticket*offers an inspiring introduction for nontechnical readers to what is surely the most important open problem in computer science."

**--Leslie Ann Goldberg,**

*LMS Newsletter**The Golden Ticket*does a good job of explaining a complex concept in terms that a secondary-school student will understand--a hard problem in its own right, even if not quite NP."

**--**

*Physics World**The Golden Ticket*] is fun to read and can be fully appreciated without any knowledge in (theoretical) computer science. Fortnow's efforts to make the difficult material accessible to non-experts should be commended."

**--Andreas Maletti,**

*Zentralblatt MATH***--Gail Kaplan,**

*Mathematics Teacher***--James M. Cargal,**

*UMAP Journal*## Endorsements

*The Golden Ticket*, I sort of hope P isn't NP after all."

**--Vint Cerf, Internet Pioneer**

**--Stephen Cook, formulator of the P-NP problem**

**--John MacCormick, author of**

*Nine Algorithms That Changed the Future***--William Gasarch, University of Maryland**

**--William J. Cook, author of**

*In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation*## Table of Contents

*Preface*ix

Chapter 1 The Golden Ticket 1

Chapter 2 The Beautiful World 11

Chapter 3 P and NP 29

Chapter 4 The Hardest Problems in NP 51

Chapter 5 The Prehistory of P versus NP 71

Chapter 6 Dealing with Hardness 89

Chapter 7 Proving P ≠ NP 109

Chapter 8 Secrets 123

Chapter 9 Quantum 143

Chapter 10 The Future 155

*Acknowledgments*163

*Chapter Notes and Sources*165

*Index*171

## Other Books Written by this Author(s)

- Lance Fortnow

## Series

## Shopping Cart Options

### For eBooks

**Many of our ebooks are available throughlibrary electronic resources including these platforms:**

Our eBook editions are available from these online vendors:

### For hardcover/paperback orders in **United States, Canada, Latin America, Asia, and Australia**

### For hardcover/paperback orders in **Europe, Africa, the Middle East, India, and Pakistan**

**Prices subject to change without notice**

### Princeton University Press

41 William Street

Princeton, New Jersey 08540 USA

webmaster@press.princeton.edu

609-258-4900

**USD Orders online, e-mail: IPSJacksonOrders@ingramcontent.com. For GBP orders online, e-mail: customer@wiley.com.
For more detailed ordering information, see: http://press.princeton.edu/ordering.html.**