I know nothing about N=NP debate, but does the claim P=NP and the existence of a...

jchonphoenix · on Jan 20, 2011

You'd be surprised. Sometimes its much harder to find hidden faulty logic in a proof for an algorithm's correctness or running time.

If I recall correctly, Ramanujan once wrote a proof for 1=2 that baffled mathematicians for quite some time before they figured out what was wrong. I believe that proof was rather short (< 1 page). For a long proof with a tiny error, things could be much worse.

sophiebits · on Jan 20, 2011

Can you find a reference for Ramanujan's "proof"? I looked briefly and can't find one, but I'd be very interested to see what the proof was.

niyazpk · on Jan 20, 2011

Here is one proof. I don't know if this can be attributed to Ramanujan.

    Let a, b be equal integers

    a = b
    a^2 = ab    // multiply by a
    a^2 + a^2 - 2ab = ab + a^2 - 2ab    // subtract a^2 - 2ab
    2(a^2 - ab) = a^2 - ab
    2 = 1

From p319, Fermat's Last Theorem by Simon Singh

sophiebits · on Jan 20, 2011

I'm guessing this isn't the proof that jchonphoenix referenced, because it has a fairly obvious error and most mathematicians would see it quite quickly.

sgk284 · on Jan 20, 2011

Just for those who don't see the error:

  2(a^2 - ab) = a^2 - ab

On this line, a^2 - ab is 0 (look at line 2). You wind up dividing both sides by 0, thus resulting in the false proof.

mitko · on Jan 20, 2011

division by zero ?

tjarratt · on Jan 20, 2011

A contradiction implies all falsehoods are true.

chrisaycock · on Jan 20, 2011

I was able to find this, though it's just some algebra tricks rather than a professional mathematician's musings:

http://www.innovatia.com/Design_Center/Proof_that_2=1.htm

flatline · on Jan 20, 2011

It certainly would make it easier for a professional programmer to verify, hence it has a certain appeal to this audience. Probably not so much for a mathematician.

MarkPNeyer · on Jan 20, 2011

If P=NP there might still be no practical implications - if there is a minimum complexity bound on the order of the polynomial, then it might remain completely impractical to solve np complete problems.