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!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: