P = NP?
People have been sending me this paper that "proves" that P != NP. These sorts of papers make the rounds regularly, and my advice is to not pay attention to any of them. G.J. Woeginger keeps a list of these papers -- he has 43 so far -- and points out:
The following paragraphs list many papers that try to contribute to the P-versus-NP question. Among all these papers, there is only a single paper that has appeared in a peer-reviewed journal, that has thoroughly been verified by the experts in the area, and whose correctness is accepted by the general research community: The paper by Mihalis Yannakakis. (And this paper does not settle the P-versus-NP question, but "just" shows that a certain approach to settling this question will never work out.)
Of course, there's a million-dollar prize for resolving the question -- so expect the flawed proofs to continue.
Posted on November 4, 2008 at 12:12 PM • 27 Comments