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

Daniel • November 4, 2008 12:40 PM

And how many papers there are “proving” the security of their crypto through reducing the underlying problem to something NP-complete! Even if NP-complete problems turn out to be strictly super-polinomial, it has no bearing whatsoever on security: complexity is concerned with worst-case behavior, whereas security depends on average and best-case behavior.

It is actually depressing that so many people misunderstand complexity theory and its uses.