Proposed proof for P not equal to NP is probably wrong

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