Monday, November 21, 2005

A short proof that a proof is probably wrong

Here's another attempt at separating NP from P, this time from the backwaters of beautiful Ernakulam in Kerala, India. The title says "NP != P and CO-NP != P", whence it follows that the proof is almost surely wrong. No self-respecting mathematician would've written the second part of the title.

(For the programming-languages-challenged, "!=" is the same as $\neq$)


Anonymous said...

I think that instead of
awarding the first person
who solve the NP vs P problem a million dollar,
we should put her/him in
jail for one year.
A read scientist will not
mind, but it will put off
those anonying guys.

Herman said...

"Those annoying guys" seek eternal fame. They believe they are right. So they will not be put off by a year in jail. On the contrary, it will add to their fame. They will be martyrs!

Real scientists, on the other hand, would not want to waste a year in jail. So they would solve the NP vs P problem under the name of some fame-seekers. Thus they can continue to do research while the fame-seekers are in jail, enjoying eternal fame.

Anonymous said...

Just to confirm the high quality of typical CoRR complexity submissions there is another recent submission that resolves the question the other way by giving a polynomial-time algorithm for circuit-SAT.

Anonymous said...

I don't think there is anything wrong with seeking eternal fame. After all, doesn't everyone seek it? Some scientific types are quick to label someone as crackpot, but just because someone finds a mistake in a proposed proof does not always mean that the author is a crackpot and that the fundamental ideas do not have any merit.

Not long ago, Louis De Branges proposed a proof for the Bieberbach conjecture. The first few attempts were flawed, but ultimately he did successfully prove it. It is unfortunate that no one has stepped forward to verify his proposed proof of the Riemann Hypothesis.

Andrei Lopatenko said...

As far as I remember Plutarch wrote in hiis book about Alexander The Great that in ancient India the discussion and proof of ideas were the most important elements of culture.
It was common that two persons disagreeing on some idea settle a public debate.
A few days or a week were given for a debate. Everybody could attend and listent to speaker. Then public or local governor decided who wins, whose orgauments were the most convinsing.
The winner get an award, the looser is beheaded.
So, one could try to participate in a discussion only in case if he was absolutely sure that he was right and could prove his point.