## P ≠ NP?

There's a new paper circulating that claims to prove that P ≠ NP. The paper has not been refereed, and I haven't seen any independent verifications or refutations. Despite the fact that the paper is by a respected researcher -- HP Lab's Vinay Deolalikar -- and not a crank, my bet is that the proof is flawed.

EDITED TO ADD (8/16): Proof seems to be seriously flawed.

EDITED TO ADD (9/11): Proof is wrong.

Posted on August 9, 2010 at 2:46 PM • 81 Comments

## Leave a comment