- Knowing the rough techniques used.
- Following the proof line by line.
- Can recreate the proof.
- Can explain the proof to others.
- If someone else claims a mistake in the proof, you can show them why they are wrong.
- Applying the proof techniques to other theorems.
Why do we understand proofs?
- Part of the job, as a referee, reviewer or advisor.
- We care about the theorem, because it is important and/or something we've worked on.
- We've heard the proof is nice and short and worth reading.
- We want to apply the proof techniques to other problems.
Now instead of the question being "what is science" the question of the day is what is art!
ReplyDeleteI sat in on three of the Knuth God and Computers lectures. On the lecture on aesthetics I asked him at the end about the use of the term "The Art of Computer Programming." To me, it is more of craft, like pot making or tapestry making. To me, art is something that communicates emotions to others.
Anyway, Knuth provided his own definition, which was more about art being beauty. There are no objective definitions everyone agrees on... but it might be a little funny that everyone says Computer Science is either an Art or a Science (or both), but no one claims that it's a philosophy. I say, just wait until Computational Theology is a required course in high school, and then we'll see if it's a philosophy.
Is this an ordered list ? It is interesting that applying a proof of one result in another context can require a varying amount of understanding: sometimes it goes through without too many modifications, and sometimes you have to get downright dirty with the proof to figure out what's working.
ReplyDeleteI don't know if it is "unfortunate" that proofs are most often read to be used. Often, you have to really understand a proof in order to either use it, or realize why it cannot be used, and then the realization of its beauty sets in. This is far truer with complex proofs, where the intricate balances that make the proof go are not immediately apparent.
You mean, a nice proof is the opposite of a cow--milked, milked, milked, and then savored.
ReplyDeleteThere are also proofs from the book. Can anybody write a chapter with neat TCS proofs?
ReplyDeleteSpeaking of beautiful proofs, check out this new (free as in beer, speech) vector graphics software.
ReplyDeleteFinally, a replacement for xfig!
-- Can anybody write a chapter with neat TCS proofs?
ReplyDeleteUwe Schoning and Prim already did that:
Gems of Theoretical Computer Science
A very nice book.
Alex Lopez-Ortiz
"Unfortunately I suspect most proofs are read with the last goal in mind [to apply the proof techniques to other problems]. A nice proof is a work of art, something to be savored, not something to be milked."
ReplyDeleteI couldn't disagree more with Lance on this last point. The more applicable a proof technique is to a variety of problems, the more valuable it is; and such usefullness will only serve to showcase the ingenuity of the person(s) who first came up with the idea and the beauty of the technique itself.
Personally, one of the first things I ask myself when reading a proof is, "what else can this technique be used for?" Sometimes this kind of thinking is actively promoted by the authors--Li & Vitanyi come to mind with the incompressibility method in Kolmogorov complexity.
I don't think this detracts at all from appreciating the art involved in a proof. (Although, I suspect the greatest creativity comes in what seems to be the most mundane activity--making the definitions. Get your definitions right and you've done 90% of the work.)
Here's my book suggestion on the topic of proof techniques: The Complexity Theory Companion by Hemaspaandra and Ogihara.