tag:blogger.com,1999:blog-3722233.post112240301461273461..comments2022-05-17T19:30:53.024-05:00Comments on Computational Complexity: Understanding ProofsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-1122524368597638412005-07-27T23:19:00.000-05:002005-07-27T23:19:00.000-05:00"Unfortunately I suspect most proofs are read with..."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."<BR/><BR/>I 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.<BR/><BR/>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.<BR/><BR/>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.)<BR/><BR/>Here's my book suggestion on the topic of proof techniques: <A HREF="http://www.amazon.com/exec/obidos/tg/detail/-/3540674195/" REL="nofollow">The Complexity Theory Companion</A> by Hemaspaandra and Ogihara.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122476341255379512005-07-27T09:59:00.000-05:002005-07-27T09:59:00.000-05:00-- Can anybody write a chapter with neat TCS proof...-- Can anybody write a chapter with neat TCS proofs?<BR/><BR/>Uwe Schoning and Prim already did that:<BR/><BR/><A HREF="http://www.amazon.com/exec/obidos/tg/detail/-/3540644253/002-7438489-5472812?v=glance" REL="nofollow">Gems of Theoretical Computer Science</A><BR/><BR/>A very nice book.<BR/><BR/>Alex Lopez-OrtizAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122458057862263672005-07-27T04:54:00.000-05:002005-07-27T04:54:00.000-05:00Speaking of beautiful proofs, check out this new (...Speaking of beautiful proofs, check out this new (free as in beer, speech) <A HREF="http://www.inkscape.org/" REL="nofollow">vector graphics software</A>.<BR/><BR/>Finally, a replacement for xfig!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122445496957416472005-07-27T01:24:00.000-05:002005-07-27T01:24:00.000-05:00There are also proofs from the book. Can anybody w...There are also <A HREF="http://www.amazon.com/exec/obidos/tg/detail/-/3540404600/cryptopointers20" REL="nofollow">proofs from the book</A>. Can anybody write a chapter with neat TCS proofs?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122435583509967332005-07-26T22:39:00.000-05:002005-07-26T22:39:00.000-05:00You mean, a nice proof is the opposite of a cow--m...You mean, a nice proof is the opposite of a cow--milked, milked, milked, and then savored.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122412301406384712005-07-26T16:11:00.000-05:002005-07-26T16:11:00.000-05:00Is this an ordered list ? It is interesting that a...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. <BR/><BR/>I 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.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122404257105053212005-07-26T13:57:00.000-05:002005-07-26T13:57:00.000-05:00Now instead of the question being "what is science...Now instead of the question being "what is science" the question of the day is what is art!<BR/><BR/>I 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.<BR/><BR/>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.Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.com