From Mathematics

The Giant’s Shoulders

“If I have seen farther it is because I have stood on the shoulders of giants,” is a quote that is often misattributed to Sir Isaac Newton, one of the two amazing minds that developed the calculus around the turn of the 18th century. While that quote is not Newton’s, it still is entirely true about his work. Without the work of the mathematicians of the previous two centuries Newton, and Leibniz, would not have been in a position to develop the calculus, an area of mathematics which can easily be argued to be the true engine behind the industrial revolution.

Mathematics, in fact all of science, is not done in a vacuum. All the work that is done today builds off of the work of generations of thinkers, inventors, and researchers. When a mathematician decides to shuck off the yoke of previous work they find themselves staring up from a hole that might as well go all the way to the center of the earth. One of the classic examples of this is the work Principia Mathematica by Bertrand Russel and Albert North Whitehead where they decided to tear down mathematics and build it back up from a foundation centered only upon the most elementary of logic. The Principia was never finished, in fact not two decades later it was proven that such a treatment of the subject could not be done, they ended up using the first 362 pages to prove the statement 1+1=2. Of course mathematicians can also find themselves indebted to someone well outside of their field. A wonderful example of this is the work of Duncan Watts and Steve Strogatz on the topic of Small World Networks which all started because Watts remembered his father once telling him that everyone is separated by only six handshakes, and idea popularized in 1929 by Frigyes Karinthy in his short story Chains.

This debt to what has come before is treated very differently by mathematicians, and while few would completely disavow what they owe none take it more seriously than Grigori Perelman. A Russian mathematician, Perelman gained international renown in November 26 for his proof of the Poincaré conjecture, one of the Clay Mathematics Millennium Problems which have a million dollar bounty on their solutions, which had stood unsolved since 1904. This work was so important and groundbreaking that in 2006 they earned Perelman the highest award that a mathematician can earn, a Fields Medal. An award that, with a mind at least partially thinking of the debt to the mathematical community that comes with accepting such a high honor, Perelman declined, citing that he did not want to displayed like a zoo animal. This was only the first award that Perelman declined, he also turned down the million dollar Millennium Prize bounty and this time his refusal was clearly to deal with debt. Perelman’s proof of the Poincaré conjecture came from following what is known as the Hamilton program, essentially a plan for producing a solution to the conjecture that was developed by American mathematician Richard Hamilton. Perelman thought that it was unjust that he alone was getting all of the accolades, and prizes, for the work and Richard Hamilton, a man to whom Perleman clearly feels a great debt, was languishing on the sidelines. There is hope that Perelman’s thoughts about the unjust nature of the mathematical community, which have cause him to withdraw from the community, may still be assuaged as Richard Hamilton was a co-award winner of the Shaw prize for the work he did towards the proof.

While Perelman’s empathy towards those whose work he used as stepping stool to new results is unusual, it is illustrative of just how important previous work is to those who really notice.

Benoit Mandelbrot, you will be missed.

Yesterday Benoit Mandelbrot, one of the most important and influential mathematicians of the past century passed away. Sadly I do not know much about the life and work of mandelbrot with the obvious exception of the Mandelbrot Set. This video by Pisut Wisessing for the Jonathon Coulton song is a wonderful send off though.

Traveling Salesmen and Indomitable Problems

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.