{"id":1778,"date":"2013-04-27T04:57:34","date_gmt":"2013-04-27T08:57:34","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1778"},"modified":"2013-04-27T04:57:34","modified_gmt":"2013-04-27T08:57:34","slug":"the-golden-ticket","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2013\/04\/27\/the-golden-ticket\/","title":{"rendered":"The Golden Ticket"},"content":{"rendered":"
\"\"<\/a>
The Golden Ticket<\/figcaption><\/figure>\n

I picked up Lance Fortnow’s<\/a> new book\u00a0The Golden Ticket: P, NP and the Search for the Impossible<\/a>.<\/em> \u00a0Lance 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<\/a> blog.<\/p>\n

The title of the book comes from the Willy Wonka<\/a> story of finding a golden ticket that allows passage into a chocolate factory and a lifetime supply of candy. \u00a0But golden tickets are rare: \u00a0how can one find one? \u00a0Can finding golden tickets be done fast? \u00a0The difficulty of finding rare items in a sea of possibilities is at the heart of the P=NP issue.<\/p>\n

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. \u00a0An initial proof leads to inefficient (but polynomial) codes which are used to improve on themselves culminating in the “Urbana algorithm” \u00a0(I bet it would be the “Carnegie Algorithm”, but this is Lance’s story):<\/p>\n

… 42 million lines of unintelligible code. \u00a0And it solved NP problems fast, very fast. [without becoming self-aware. \u00a0No Skynet in this book.]<\/p><\/blockquote>\n

Lance then explores the effect of the Urbana algorithm. \u00a0 \u00a0Some of his predictions seem a bit far-fetched. \u00a0I 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.<\/p>\n

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:<\/p>\n

First, of course, is the schedule of this particular game. \u00a0As late as 2004, a husband-and-wife team, Henry and Holly Stephenson, scheduled games for Major League Baseball. \u00a0They 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]. \u00a0In 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.<\/p><\/blockquote>\n

Hey, that’s me! \u00a0I made it into Lance’s book! \u00a0Well, me and my colleagues at the Sports Scheduling Group<\/a>. \u00a0Lance goes on to say a few more words about the effect of the Urbana algorithm on scheduling:<\/p>\n

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. \u00a0Handling 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 \u00a0a matter of minutes.<\/p><\/blockquote>\n

If I were to continue the story, I would include something Lance did not: \u00a0the Sports Scheduling Group would likely have gone out of business shortly after the release of the Urbana algorithm. \u00a0While 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). \u00a0In 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. \u00a0In Warren Buffet’s terms, computational complexity is our business’s moat<\/a>, preventing others from following too easily.<\/p>\n

So far, I love the book (and not just because of the shout-out!). \u00a0It is a book on a technical subject aimed at a general audience. \u00a0I’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.<\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

I picked up Lance Fortnow’s new book\u00a0The Golden Ticket: P, NP and the Search for the Impossible. \u00a0Lance 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 … Continue reading “The Golden Ticket”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,51],"tags":[],"class_list":["post-1778","post","type-post","status-publish","format-standard","hentry","category-books","category-sports"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1778","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1778"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1778\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1778"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1778"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1778"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}