not again!

Since I only recently started reading ArXiV through my RSS aggregator, I was a unaware of the astonishing regularity with which “proofs” of polynomial-time algorithms for NP-complete problems are proposed. Most recent is this one, but one can find a more comprehensive list here. The latter page is a bit too unskeptical of the claims, since they say “so and so proved P=NP in this paper.” It’s not a proof if it’s wrong, and pretty much all of these proofs have been shown to be wrong. But it might be an interesting exercise one week for some reading group or topics class to formally prove some of these guys wrong. Of course, for every person claiming a proof that P=NP there is another person ready to knock them down and claim that P!=NP. Maybe it’s just a little self-correcting mechanism in the ArXiV.

Advertisements