4 ms·
I know nothing about N=NP debate, but does the claim P=NP and the existence of a published algorithm (https://github.com/anjlab/sat3 https://github.com/anjlab/s
by equark 16y ago
I know nothing about N=NP debate, but does the claim P=NP and the existence of a published algorithm (https://github.com/anjlab/sat3 https://github.com/anjlab/sat3) make this claim easier to verify than the claim P!=NP. Isn't the point that P=NP has great practical significance that will be immediately recognized?
- MarkPNeyer 16y agoIf 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.
- flatline 16y agoIt 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.
- jchonphoenix 16y agoYou'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.
- spicyj 16y agoCan 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.
- chrisaycock 16y agoI 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 http://www.innovatia.com/Design_Center/Proof_that_2=1.htm
- niyazpk 16y agoHere 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
- sgk284 16y agoJust 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 16y agodivision by zero ?
- tjarratt 16y agoA contradiction implies all falsehoods are true.
- spicyj 16y agoI'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.