The Golden Ticket: P, NP, and the Search for the Impossible
“. . . high praise.”
The title The Golden Ticket is taken from Roald Dahl’s Charlie and the Chocolate Factory.
Dr. Fortnow explains his reference: Dahl’s book has a machine that can tell if there is a golden ticket inside the wrapper of a candy bar without opening the wrapper. The intent of The Golden Ticket is to consider the possibility of a real-world algorithmical equivalent of Dahl’s fictional machine to solve certain classes of mathematical problems.
Whether or not quick solutions exist for all algorithmical problems is in computer science referred to as the P versus NP problem. “P” indicates the class of problems that can be solved (relatively) quickly by computer and “NP” indicates the class where today’s fastest computers could take longer than the age of the universe to complete.
The P versus NP problem has been previously addressed in popular science texts, a few have been reviewed here: Visions of Infinity by Ian Stewart and In Pursuit of the Traveling Salesman by William J. Cook. In fact so many academic papers have been written on this topic that it has strained the ability of reviewers to keep up.
The journal Communications of the ACM has even put in a rule: if you submit a paper on the topic of P versus NP, you are not permitted to submit another for 24 months. Lance Fortnow’s article on P versus NP, published in Communications of the ACM in 2009 quickly became that journal’s most downloaded article ever and led directly to the creation of this book.
The P versus NP problem remains an unanswered question, whether every problem whose solution can be quickly checked can also be quickly solved. If P equals NP then every problem in NP can be computed quickly. If P doesn’t equal NP then there will always remain mathematical problems that can’t be solved quickly.
The P versus NP problem is also a way of reasoning about computational complexity. Alan Turing first identified computational complexity with the “halting problem,” the most familiar example involving the hourglass or ball (also known as the spinning beach ball from hell) you get when your computer does not immediately respond. You ask yourself: Is the computer taking a long time to think or is it stuck?
The solution to the P versus NP problem is so valuable that there is a million-dollar prize offered by the Clay Mathematics Institute. The P versus NP problem is just one of the institution’s seven Millennium Prize problems, though if you solve P versus NP, you have a head start on the others.
One example of a practical problem in NP is the “travelling salesman” problem. Given a number of cities, calculate the shortest path that goes through all the cities. To solve the travelling salesman problem you would have to determine all possible paths (a hard problem) before you could begin to choose the shortest path (an easy problem). The result of calculating all possible paths for traversing the capitals of the 48 contiguous states has 62 digits! And BTW, solving the traveling salesman problem wins you another Millennium Prize.
The nature of the P versus NP problem has been hinted at by many mathematicians and philosophers including William of Ockham, memorialized for Occam’s razor: The simplest solution is usually the best. And Einstein who said, ”Make everything as simple as possible, but not simpler.” The limitation with sayings like these is that knowing simple is good isn’t good enough. They don’t tell us how to make things simple or whether a solution is the simplest of all possible solutions.
The honor of identifying P versus NP goes back to the mathematicians Kurt Gödel and John Von Neumann, determined from a personal letter written in 1956 that was lost and not rediscovered until the 1980s.
The P versus NP problem was publicly announced in 1971 with a paper written by the mathematician Stephen Cook. In 1972 the computer scientist Richard Karp identified 21 important computationally complex problems that capture the essence of P versus NP. After Karp’s paper was published, computer scientists acknowledged the significance of P versus NP.
The discovery of P versus NP also followed independent paths in the East and the West. At the same time that Steve Cook and Richard Karp were creating its foundations in the West, so were Leonid Levin, Sergey Yablonsky, and Andrey Kolmorgorov on the other side of the Iron Curtain. The Soviet study of P versus NP went under a branch of science called Theoretical Cybernetics.
Dr. Fortnow playfully imagines the consequences if P were proven to equal NP. The future holds a cure for cancer, perfect weather prediction, perfect voice recognition, perfect language translation, and real-time 3D graphics rendering. Computers would be so fast and accurate that software programs replace human umpires for sporting events (though that is happening right now in soccer—without having to solve P versus NP).
Dr. Fortnow also addresses machine learning by asking the question, how can a computer read handwriting when everyone’s is different? He points out another machine learning advance, “recommender” systems used by Amazon and Pandora for suggesting books and music. Dr. Fortnow extends what can be done today into the future: having a computer write a novel specifically for you (and not by simply slipping your name into a template) by creating a unique story tailored to your interests. Computers of the future could also write speeches uniquely tailored to audiences, and fight crime by generating physical sketches of suspects based on DNA found at crime scenes.
Today our inability to quickly solve NP problems is a two-edged sword. We have secure transactions on the Internet today because of the difficulty in factoring large primes. In this respect, the possibility that P could eventually be proven to equal NP offers its dark side—by factoring primes quickly it becomes very easy to crack public key cryptography, breaking security on the Internet. The author also makes a beginner’s mistake however by saying private key cryptography could be used as a backstop, not realizing that distribution of private keys over the Internet is only practical through secure public key cryptography.
Dr. Fortnow also offers the reader a game based on an imaginary world called “Frenemy.” In Frenemy people are grouped by chains of associations of friends and enemies. The purpose of the game is to determine the effort needed to discover new associations. The reader learns that the discovery of simple associations can be algorithmically complex though matches could be solved in reasonable time if the cost of computation were low, that is, if P equaled NP.
The application of Frenemy to the real world is that the algorithms for finding relationships correspond to reverse engineering anonymized data used to assure privacy while sharing redacted medical, telecom, insurance, merchant, and social network data. (And again, redacted associations can be efficiently recovered today without solving the P versus NP problem).
Quick algorithms for discovering associations or “matchmaking” can also be applied to games such as Sudoku, Minesweeper and Tetris, as well as be used to solve important problems in science.
Dr. Fortnow points out the value for speedier matchmaking in biology, for example, quicker DNA sequencing and protein folding. For physics, speedier finding of minimum energy states in complex systems. Economics would be served through a speedup in linear programming algorithms, and problems in number theory could be solved by faster proof finding.
What is a computer scientist to do if P is never proven to equal NP? Sometimes you just have to keep trying. When there’s no best solution to be had, non-optimal solutions can be found by heuristics or rules of thumb. An example of heuristics is given for determining the minimum number of colors needed to color an arbitrary map. Here Dr. Fortnow’s explanation is intricate and a reader might be better served if the illustrations that were provided had been in color—the irony of the penny-wise, pound-foolish publisher.
Dr. Fortnow also considers problems that lie in-between, that is, problems that are hard to solve but don’t quite hit the threshold of NP. In many instances NP problems get easier to solve as the number of elements to calculate decrease (for example, fewer cities to traverse in the traveling salesman problem).
For problems below a certain size (that can be parallelized), one can just throw on more computers. Getting a solution by simplifying the problem or by brute force may not be elegant but may be good enough until something better comes along.
The end chapters cover current challenges for computing, including quantum computing, quantum cryptography, and quantum teleportation. Quantum computing, if (or when) the technical issues can be solved would speed up some but not all NP problems. As to which depends on the algebraic structure.
Dr. Fortnow expects P to eventually be proven to not equal NP though he also expects this question to remain unresolved for a very long time. He notes the difficulty might hinge on a paradox first identified by Gödel that there are mathematically true statements that cannot be proven true.
Though Dr. Fortnow explains P versus NP clearly and simply, The Golden Ticket gets fairly involved in two sections: zero-knowledge proofs and heuristics for determining the minimum number of colors (illustrations handicapped by a lack of color).
Dr. Fortnow has a playful writing style reminiscent of Douglas R. Hofstadter’s Gödel, Escher, Bach, which should be taken as high praise. Looking forward to Dr. Fortnow’s next book.