Last week's top news was Vinay Deolalikar's attempted proof of P≠NP. After a flurry of discussion over the weekend, a consensus has formed that Deolalikar's paper, although well thought-out, falls short of delivering.
Coverage of the episode mostly polarized between mainstream media outlets who could only scratch the problem's definition without giving any details on the solution, and theoretical computing blogs which delved into the subject far deeper than even the average Computer Science graduate (myself included) could follow. Trying to read the paper itself provided little relief either.
One of the few resources to strike a balance – deep enough so as to give the gist of the solution and its counter-arguments, but not too deep to the uninitiated – was Scott Aaronson's Shtetl-Optimized blog. Aaronson was involved in a bit of a spat over his US$ 200,000 bet that Deolalikar's proof wouldn't stand, but otherwise his articles on the episode provide the most complete reading I could actually understand:
Besides being worth reading on their own, both articles provide a wealth of references for those who'd like to dig deeper – whether or not you'd care to take a shot at that US$ 1,000,000 prize.
