News for hackers. Stuff that matters.
Re:Proofs By Contradiction And Other Dangers by kenjackson on Saturday January 08, 2011 @08:37PM (#2084529)
Proof by contradiction requires a high degree of precision because the desired result is a false statement. Whereas, for example, proof by construction requires an exactly correct answer.

For example, proving a^2 + b^2 = c^2 by construction requires ending up with the exact correct answer. Ending with a^1.8 + b^2.5 = c^3 isn't good enough. You may not know where the problem in your proof is, but you know there's a problem.

Whereas with contradiction you just get something like 1 == 2, which is clearly false. So did you arrive at that because of the contradiction or a mistake in the proof? Its really impossible to know.

With that said, I must admit that contradition feels like the only way to prove NP/P -- although I'm not a theorist and don't really know the latest techniques, but just from an amateur it seems that contrapositive/construction/direct/etc allow for solutions to this problem.

There are no comments on this comment yet.