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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.