Tuesday, August 10, 2010

P is not equal to NP?

Vinay Deolalikar a research scientist at HP labs, has a preprint (on his web page) which is a preliminary draft of a proof that P is not equal to NP. Claimed resolutions of P=NP are rife on the internet. However, this draft preprint is from a reputable researcher. The P=NP question is one of the most important research problems of our time. Any proof of this importance will have to be carefully checked by the research community. We shall see!

See how this process has been playing out as of August 16, 2010: Step 1: Post Elusive Proof. Step 2: Watch Fireworks. in the New York Times.

See also A Tale of A Serious Attempt At P≠NP by Computer Scientist Richard J. Lipton at CACM.