- Proof by blatant assertion: this is marked by expressions like "obviously", "trivially", "any moron can see that".
- Proof by example: you sketch a proof that the theorem is true for n = 4, and claim that this proof generalizes to all n.
- Proof by picture: picture + handwaving makes a pretty compelling argument in a classroom.
- Proof by omission: we state the theorem and the proof is left as an exercise for the reader.
- Proof by accumulated evidence: for three decades we have worked very hard to produce an efficient algorithm for NP-complete problems without results; therefore P != NP.
- Proof by reference to famous people: I saw Karp on the elevator, and he thought that our problem is NP-complete!
- Proof by confusion: P = NP <=> P - NP = 0 <=> P(1-N) = 0 <=> P = 0 or N = 1; but the last expression is false and therefore P != NP.
What are your favorite proof techniques?
2 comments:
It was fun reading this one! I have recently started reading your blog and it is really good. Keep up the good work.
Hey, thanks for the encouragement!
Post a Comment