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

THE GOLDEN TICKET

THE GOLDEN TICKET

P, NP, AND THE SEARCH FOR THE IMPOSSIBLE

LANCE FORTNOW

PRINCETON UNIVERSITY PRESS

PRINCETON AND OXFORD

Copyright 2013 by Princeton University Press

Published by Princeton University Press, 41 William Street, Princeton, New Jersey 08540

In the United Kingdom: Princeton University Press, 6 Oxford Street,

Woodstock, Oxfordshire OX20 1TW

press.princeton.edu

The epigraph for this book is taken from Charlie and the Chocolate Factory by Roald Dahl, copyright 1964, renewed 1992 by Roald Dahl Nominee Limited. Used by permission of Alfred A. Knopf, an imprint of Random House Childrens Books, a division of Random House, Inc. Any third party use of this material, outside of this publication, is prohibited. Interested parties must apply directly to Random House, Inc. for permission.

All Rights Reserved

Library of Congress Cataloging-in-Publication Data

Fortnow, Lance, 1963

The golden ticket : P, NP, and the search for the impossible / Lance Fortnow.

pages cm

Summary: The P-NP problem is the most important open problem in computer science, if not all of mathematics. 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. In this informative and entertaining book, Lance Fortnow traces how the problem arose during the Cold War on both sides of the Iron Curtain, and gives examples of the problem 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. But difficulty also has its advantages. Hard problems allow us to safely conduct electronic commerce and maintain privacy in our online lives. The Golden Ticket explores what we truly can and cannot achieve computationally, describing the benefits and unexpected challenges of the P-NP problemProvided by publisher.

Includes bibliographical references and index.

ISBN 978-0-691-15649-1 (hardback)

1. NP-complete problems. 2. Computer algorithms. I. Title.

QA267.7.F67 2013

511.352dc23

2012039523

British Library Cataloging-in-Publication Data is available

This book has been composed in Minion Pro

Printed on acid-free paper.

Printed in the United States of America

1 3 5 7 9 10 8 6 4 2

To Marcy, Annie, and Molly,

SO THAT THEY MAY KNOW WHAT I DO AND WHY I DO IT.

In England the famous scientist Professor Foulbody invented a machine which would tell you at once, without opening the wrapper of a candy bar, whether or not there was a Golden Ticket hidden underneath. The machine had a mechanical arm that shot out with tremendous force and grabbed hold of anything that had the slightest bit of gold inside it and, for a moment, it looked like the answer to everything.

Roald Dahl, Charlie and the Chocolate Factory

Contents

Preface

NEARLY HALF OF AMERICANS CARRY A SMARTPHONE, a computer more powerful than the supercomputers of just a couple of decades ago. Computers bring us the worlds information and help us sort through it. Computers allow us to communicate with almost anyone, anywhere. Computers can perform tremendous computations, from simulating cosmic events to scheduling complex airline routes. Computers can recognize our voices, our faces, our movements. Computers can learn our preferences and tell us what books, music, and movies we may like. In the not too distant future, computer technology will allow our cars to drive themselves. There seems to be no limit to what computers can do.

Or is there? This book explores the computational problems that we may never be able to compute easily. It does so through the most important challenge in computer science, if not all of mathematics and science, the oddly named P versus NP problem.

P versus NP is a mathematical challenge, one of seven recognized as a Millennium Prize Problem by the Clay Mathematics Institute, which puts a million-dollar bounty on its solution. But P versus NP means so much more.

P refers to the problems we can solve quickly using computers. NP refers to the problems to which we would like to find the best solution. If P = NP, then we can easily find the solution to every problem we would like to solve. If P = NP, then society as we know it would change dramatically, with immediate, amazing advances in medicine, science, and entertainment and the automation of nearly every human task.

If P NP, by contrast, then there are some problems we cannot hope to solve quickly. Thats not the end of the story, as we can create techniques that help us attack these problems in many cases. P NP means there is no automated way to solve some of the problems we want to solve. Still, knowing which tools dont work can help us figure out which ones do.

In August 2008, Moshe Vardi, editor-in-chief of the Communications of the ACM , asked me to write an article on the P versus NP problem. The Association for Computing Machinery is a major society serving computing researchers and professionals, and Communications is the societys main magazine devoted to articles of interest for that community.

At first I tried to push the article onto another computer scientist, but eventually relented. As Moshe put it to me, If physicists write popular articles (and books) about string theory, we should be able to explain what complexity theory has accomplished, Id hope. I wrote the article, aiming for the Communications audience, not just about the status of the P versus NP problem, which can be summarized as still open, but about how people deal with hard problems. The Status of the P versus NP Problem was published in the September 2009 issue and quickly became the most downloaded article in the Communications history.

The P versus NP problem remained a story to be told, and the popularity of the article suggested the time was right to tell this story, not just to scientists but to a much broader audience.

I used that short article as a framework for this book. Sections of the article become chapters here. I also took inspiration from Stephen Hawkings A Brief History of Time , which explains physics not through formulas and technicalities but with examples and stories. I attempt to do the same here to explore the spirit and importance of the P versus NP problem.

You will not find a formal definition of the P versus NP problem here; there are many great textbooks and websites that explore the definition of and technical results related to P versus NP. Reading this book will instead give you an appreciation of the possibilities and limits of computations as computers become such an integral part of our world.

Onward to P and NP!

Lance Fortnow
Evanston, Illinois

THE GOLDEN TICKET

A CANDY MANUFACTURER DECIDES TO RUN A CONTEST and places a handful of golden tickets inside its chocolate bars, hidden among the tens of millions of bars produced each year. The finders of these tickets will get a rare factory tour.