tag:blogger.com,1999:blog-3722233.post3430726590124142850..comments2024-03-18T17:27:11.613-05:00Comments on Computational Complexity: Models versus ProofsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-9654353964882697152009-09-11T08:27:18.030-05:002009-09-11T08:27:18.030-05:00Isn't a good part of your own research (namely...Isn't a good part of your own research (namely the oracle stuff) well on the proof side?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36844892908591902652009-09-11T06:29:16.820-05:002009-09-11T06:29:16.820-05:00A quote from this short article by Paul Krugman: S...A quote from <a href="http://krugman.blogs.nytimes.com/2009/09/11/mathematics-and-economics/" rel="nofollow">this short article</a> by Paul Krugman: <i>So by all means let’s have math in economics — but as our servant, not our master.</i>Paul Goldberghttps://www.blogger.com/profile/10952445127830395305noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30146967518414387962009-09-10T20:38:30.037-05:002009-09-10T20:38:30.037-05:00At the end of the day, economic theories need to m...At the end of the day, economic theories need to match real-world data. That's why the model is so important.<br /><br />In TCS, many of our models have become completely divorced from reality (because the realistic models are too hard to analyze). This is not a good thing.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60800624954234750662009-09-10T19:11:45.840-05:002009-09-10T19:11:45.840-05:00I agree that we should pay more attention to askin...I agree that we should pay more attention to asking the <i>right questions</i> (includes models) and a bit less attention to <i>answering</i> every question we see (proofs).<br /><br />Several Turing awards and Nobel prizes have been given for asking non-obvious questions with relatively straightforward answers. Special relativity is the answer to the question <i>what follows from assuming that all inertial frames of reference are equally valid?</i> The theory of NP-completeness is the answer to the question (from abstract of Cooke's paper) <i>[Is it the case that] any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology [?]</i> Turing's seminal paper was also a lengthy but relatively routine answer to an innovative question (as noted in fake review on <a href="http://scottaaronson.com/blog/?p=253" rel="nofollow">Scott's blog</a>).<br /><br />The answers to these questions look completely trivial today since everyone has learned the techniques used. I suspect that at the time these proofs were innovative but most top researchers could have invented those techniques if they had tried to solve those problems.<br /><br />It seems rather strange for our field to give asking and answering questions similar weight when choosing Turing awards while valuing answering questions far more highly when choosing conference programs.Unknownhttps://www.blogger.com/profile/01106301822827737278noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72482428125221869302009-09-10T09:56:34.544-05:002009-09-10T09:56:34.544-05:00... I guess that's another "cultural"...... I guess that's another "cultural" difference between communities.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54709189404026856792009-09-10T09:55:11.526-05:002009-09-10T09:55:11.526-05:00It's interesting that for me the title "m...It's interesting that for me the title "models versus proofs" meant something completely different, until I read the post. Automatic theorem provers (e.g., SMT provers) eat a first-order logic formula and either say that it's a unsatisfiable (and perhaps give you a <i>proof</i> tree) or give you back a probable <i>model</i>.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.com