## 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.

barbie • August 9, 2010 3:07 PM

Most proofs that are that complex usually have some minor flaws, but not necessarily fatal ones.

Any reason you think this one is flawed ? and do you mean typo-flawed, or major-flawed ?