I picked up Lance Fortnow’s new book The Golden Ticket: P, NP and the Search for the Impossible. Lance is chair of the School of Computer Science at my alma mater Georgia Tech (I got my PhD there in Industrial Engineering) and the co-author of the excellent Computational Complexity blog.
The title of the book comes from the Willy Wonka story of finding a golden ticket that allows passage into a chocolate factory and a lifetime supply of candy. But golden tickets are rare: how can one find one? Can finding golden tickets be done fast? The difficulty of finding rare items in a sea of possibilities is at the heart of the P=NP issue.
After a brief introduction to the sort of problems that are in NP (problems whose solution can be checked quickly, with some being in P, problems whose solution can be found quickly), Lance moves on to an extended fantasy of what would happen if a proof of P=NP (in other words: problems whose solutions can be checked quickly can also have their solutions found quickly) were to be discovered. An initial proof leads to inefficient (but polynomial) codes which are used to improve on themselves culminating in the “Urbana algorithm” (I bet it would be the “Carnegie Algorithm”, but this is Lance’s story):
… 42 million lines of unintelligible code. And it solved NP problems fast, very fast. [without becoming self-aware. No Skynet in this book.]
Lance then explores the effect of the Urbana algorithm. Some of his predictions seem a bit far-fetched. I don’t think the difficulty in predicting snow storms a year in advance (as he suggests will happen) is an issue of algorithm speed, but rather limits on data availability and modeling limits, but, again, this is Lance’s fantasy so I really shouldn’t quibble.
One of Lance’s stories has a father and daughter going to a baseball game, and the father muses on the effect the Urbana algorithm has had on baseball:
First, of course, is the schedule of this particular game. As late as 2004, a husband-and-wife team, Henry and Holly Stephenson, scheduled games for Major League Baseball. They used a few simple rules, like the number of games played at home and away by each team, and some local quirks, like the Boston Red Sox like to host a daytime baseball game on Patriot’s Day in mid-April, as the runners in the Boston Marathon pass nearby [a story that takes on a whole different flavor now]. In 2005, Major League Baseball contracted with a Pittsburgh company, the Sports Scheduling Group, because its scheduling could better avoid teams playing each other in consecutive weeks.
Hey, that’s me! I made it into Lance’s book! Well, me and my colleagues at the Sports Scheduling Group. Lance goes on to say a few more words about the effect of the Urbana algorithm on scheduling:
So the baseball czars want to schedule games in a way that everyone has the best possible weather and good teams play each other at the end of the season, not to mention more mundane cost savings like reducing the amount of travel for each team. Handling all these issues and the multitude of possible schedules would have been impossible a mere fifteen years ago [the story is based in 2026], but the Urban algorithm spits out the best schedule in a matter of minutes.
If I were to continue the story, I would include something Lance did not: the Sports Scheduling Group would likely have gone out of business shortly after the release of the Urbana algorithm. While part of our skill is understanding sports leagues, a big part of our competitive advantage is that we can solve sports scheduling problems pretty darn quickly, despite the fact they are all NP-complete (the hardest of the NP problems). In short, while a proof of P=NP might be a golden ticket for some, our golden ticket is is the difficulty caused by P <> NP. In Warren Buffet’s terms, computational complexity is our business’s moat, preventing others from following too easily.
So far, I love the book (and not just because of the shout-out!). It is a book on a technical subject aimed at a general audience. I’m only partway through (I am kinda stuck on showing the baseball story to those around me), but Lance’s mix of technical accuracy with evocative story telling works for me so far.