Scott Aaronson, on his Shtetl-Optimized blog, points out Eight signs that a proposed P≠NP proof is wrong.
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. The first reason is that we’re not going to separate k-SAT from much easier problems purely by looking at the structure of the solution space:
Scott’s next article is the useful P vs NP for dummies.
The short answer is: the biggest unsolved problem of theoretical computer science, and one of the deepest questions ever asked by human beings!
Advertisements
Leave a Reply