Saturday, October 15, 2005

Fun Proof Techniques

About three years ago, I took a course on the theory of computation. I remember that during the second lecture, our instructor introduced us to the mathematical background, and in particular proof techniques. He started saying "in mathematics, we have proof by induction, proof by construction, and proof by contradiction ...". Before he finished the lecture, he presented to us a list of fun proof techniques which work in practice, some of which are listed here. My favorite ones are:

  1. Proof by blatant assertion: this is marked by expressions like "obviously", "trivially", "any moron can see that".
  2. Proof by example: you sketch a proof that the theorem is true for n = 4, and claim that this proof generalizes to all n.
  3. Proof by picture: picture + handwaving makes a pretty compelling argument in a classroom.
  4. Proof by omission: we state the theorem and the proof is left as an exercise for the reader.
  5. 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.
  6. Proof by reference to famous people: I saw Karp on the elevator, and he thought that our problem is NP-complete!
  7. 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:

Anonymous said...

It was fun reading this one! I have recently started reading your blog and it is really good. Keep up the good work.

twidjaja said...

Hey, thanks for the encouragement!