A salesman has to travel to 100 different cities in the United States in order to sell his wares, but he has a small budget and needs to maximize the amount of profit he can make from this sales trip. He decides the best way to do this is to travel to each city exactly once, and all he has to do is figure out the cheapest possible way to do it. This may not seem like a very topical, or very important, problem but it is at the heart of one of the biggest problems in mathematics and computer science today. This problem is known as the Traveling Salesman Problem; more formally stated as: Given a set of cities and the distances that are between them, what is the shortest tour that visits every city exactly once? First formulated in the 1930s mathematicians, and later computer scientists, have long attempted to find a way to answer this problem quickly and they have all failed. It was not until the 1970s that an understanding began to emerge as to why no such fast algorithm seemed possible, since it was then that a version of the Traveling Salesman Problem was shown to belong to a group of problems that are known as NP-Complete.
NP is an acronym for the even less parseable, Non-Deterministic Polynomial Time. NP problems, at their core, are simply problems that have a solution that can be shown to be true or false quickly. This differs from P, or Polynomial Time, problems in that P problems’ answers can be both found and verified quickly. In both of these cases the term “quickly” refers to speed relative to the size of the input for the problem, such as the total amount of cities for the Traveling Salesman Problem since verifying a result for 100 cities clearly takes less time that a result for 1000. NP-Complete problems, a name bestowed upon the group of problems by Stephen Cook in 1971, such as the Traveling Salesman are a special group of NP problems that have an algorithm that belongs to the P-Time that allows one to translate any NP problem into any of the NP-Complete group. A trait that really becomes important when one starts to wonder what the relationship between NP and P could be. Specifically, does P=NP?
The reason the NP-Complete group is so important to this question follows from the fact that if a person could find a P-Time solution to any NP-Complete problem that would mean that there would be a P-Time solution for all NP problems, in other words P=NP. No one has done this though, and most leading computer scientists, such as MIT’s Scott Aaronson and Northwestern’s Lance Fortnow, are on record saying that they do not believe P=NP. This would be the end of the story except no seems to be able to prove that P does not equal NP either. Not that any of the theoreticians needed more impetus to study the problem but P vs. NP, as it is known, has garnered such importance that is was named as one of the seven Clay Institute of Mathematics Millenium problems. These seven problems carry with them a bounty of $1,000,000 if a successful proof is found. As can be imagined, this announcement has spawned many proofs but none of them have held up and P vs. NP always comes out unsolved.
Unblemished records such as P vs. Np’s come under fire by those that want the scalp of the unbeaten on their mantle, especially if that scalp comes with a rather large check, but no truly serious challenger’s proof in either direction had lasted much more than a day. In fact most were crank work and dismissed as such. That was until the beginning of August 2010 when the Mathematics and Computer Science sphere of the Twitter Universe all of a sudden exploded about a new proof that P does not equal NP. The things that the twitterers most latched onto were that it was, as Lev Reyzin(@lreyzin) stated, “A Serious Paper” hence not crank work and that the author, Vinay Deolalikar, was a respected researcher who worked as Principal Research Scientist at Hewlett Packard Labs hence not a crank.
Deolalikar’s proof was contained in a 100+ page paper that was still in preliminary form when he decided to send it to colleagues for comment and review. The paper made its way around until it found itself in the email inbox of Greg Baker from Simon Fraser University who posted the first, Deolalikar soon posted a slightly update version himself, copy available for public consumption on his blog on August 7th. “A serious claim to have solved P vs. NP,” as stated by Stephen Cook himself, is not the type of thing that was going to stay quiet, but I doubt anyone could have guessed how quickly the story would spread. Within days of being posted the paper was Slashdotted, boingboinged, dugg, stumbledupon, and featured in many more traditional media outlets, such as the New York Times. Everyone wanted to tell the story of the indomitable problem finally being defeated, even though there was a definite undercurrent among the theoretical community that was more on the side of disbelief than hope of an finally having an answer. It could be that they wanted the proof to fail as they wanted the million themselves; perhaps they honestly thought that the proof was flawed, as Scott Aaronson so obviously did when he pledged to supplement the Clay prize with a $200,000 check of his own if this proof held up to close scrutiny; but there seemed to be some people who just did not want the problem to fall, that simply wanted the monument of P vs. NP still standing tall when they overlooked the landscape of Computer Science.
The close scrutiny that Aaronson thought would cause the proof to collapse happened soon enough. Within days the conversation about the proof had shifted from the “Wow this happened,” stage to “Come one boys, let us check this out,” with a core group of well respected theoreticians, including two Fields medalists, the highest award in mathematics, Timothy Gowers and Terrance Tao, leading the way in checking Deolalikar’s work. A Georgia Tech computer scientist Richard Lipton’s blog soon became the go to resource for information on the continuing process of verifying the proof, and the titles of the posts form a very concise story of the verification. August 8th was Lipton’s first entry, “A Proof that P is not Equal to NP?”, quickly followed by “Deolalikar Responds To Issues About His P does not Equal NP Proof” on the 11th, and then “Fatal Flaws in Deolalikar’s Proof?” for August 12th. While discussion is still occurring about the veracity of the proof, the communities thoughts from those five days between August 7th and 12th that is best summed up in an excerpt from Scott Aaronson’s blog, “As of this writing, Vinay Deolalikar still hasn’t retracted his P≠NP claim, but a clear consensus has emerged that the proof, as it stands, is fatally flawed.”
P vs. NP, assaulted and challenged again, remains the tallest unscaled mountain in Computer Science.