- 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