Thank God it is not P = NP

Last Friday the news broke that someone has proved that P ≠ NP (read P is not equal to NP), answering one of the age-old problems in computer science. In simplest terms, this amounts to saying that there are some problems that cannot be solved easily on computers, no matter how fast the processor is.

The proof (rather claimed proof) is spread over hundred-odd pages. The person who did it seemed serious -- he sent it to some people who are really good in the business, to check if the proof was foolproof. The mail got forwarded in many directions and someone immediately posted it on the net (yes, I think it was a silly thing to do), and the name Vinay Deolalikar became familiar in a day. Mailboxes flooded with queries about the correctness of the proof. (I came to know about all this only yesterday, as I was traveling this weekend).

Some people were sceptical about the proof, and justifiably so. Scott Aaronson literally bet his house on it. He said in response to one comment on his post: "If P≠NP has indeed been proved, my life will change so dramatically that having to pay $200,000 will be the least of it."

That explains the seriousness of the proof. If a USD $1,000,000 prize money announced for this problem was not proof enough.

One my friend said, thank god he did not prove P is equal to NP. As that would mean all 'hard' problems in computer science have a solution that can run in a reasonable time on a computer, and many people like him (and me) would become jobless.

This is the latest update I have seen: Issues in the Proof that P≠NP (Dick Lipton's blog).

But is is not dismissing this as yet another publicity gimmick. "..the author has advanced serious and refreshingly new ideas of definite value, and deserves time and space to develop them more fully", says Lipton. Which means even if the proof is not complete, it is likely to lead us to a correct and complete proof in the near future.

The paper can be found here (pdf).

Who is Grisha Perelman?

I first heard this name about a week back. I got a mail which carried a Newyork Times article dated August 15, that started with a question "Grisha Perelman, where are you?"

I didn't know who he was, but the first few lines caught my attention so I didn't delete it. It went thus:

"Three years ago, a Russian mathematician by the name of Grigory Perelman, a k a Grisha, in St. Petersburg, announced that he had solved a famous and intractable mathematical problem, known as the Poincaré conjecture, about the nature of space.

After posting a few short papers on the Internet and making a whirlwind lecture tour of the United States, Dr. Perelman disappeared back into the Russian woods in the spring of 2003, leaving the world's mathematicians to pick up the pieces and decide if he was right.."

The article goes on:

"Now they say they have finished his work, and the evidence is circulating among scholars in the form of three book-length papers with about 1,000 pages of dense mathematics and prose between them.

As a result there is a growing feeling, a cautious optimism that they have finally achieved a landmark not just of mathematics, but of human thought.."

....

"But at the moment of his putative triumph, Dr. Perelman is nowhere in sight. He is an odds-on favorite to win a Fields Medal, math's version of the Nobel Prize, when the International Mathematics Union convenes in Madrid next Tuesday. But there is no indication whether he will show up.

Also left hanging, for now, is $1 million offered by the Clay Mathematics Institute in Cambridge, Mass., for the first published proof of the conjecture, one of seven outstanding questions for which they offered a ransom back at the beginning of the millennium.."

The Fields Medal (it is awarded once in four years to mathematicians under 40, see Mathworld and wikipedia entries) was announced day before, and Perelman did win it. As expected, he declined to accept the award or appear at the congress (International Congress of the International Mathematical Union, where the award ceremony is held).

It seems to have become an added motivation for the "investigative" journos to come up with more masala and more drama. Latest gossip that is making rounds is that the guy was fired from the Institute he was working at, and he now lives with his mother's pension money, and also that he does not want to talk about Mathematics. (Could be true.)

All this would have made mathematitians happy. It is not every day that mathematics is in news! [Also see http://en.wikipedia.org/wiki/Grigori_Perelman].