tag:blogger.com,1999:blog-3722233.post5050515664536523011..comments2022-05-24T23:04:24.301-05:00Comments on Computational Complexity: What is an application?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-12676837449950818362008-05-12T15:48:00.000-05:002008-05-12T15:48:00.000-05:00I just submitted a paper that shows an absolute ti...I just submitted a paper that shows an absolute time lower bound for stochastic models of nano self-assembly, using the Naor and Stockmeyer paper I first found on your "Applications of Ramsey Theory" page. Applications are where you find them... and thank you, Bill!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2016020612606110202008-05-12T12:35:00.000-05:002008-05-12T12:35:00.000-05:00One criterion in judging the worth of an applicati...One criterion in judging the worth of an application of a complex theory: How much of the complexity of the theory is needed to derive the consequence?<BR/><BR/>A much simpler case than the ones you mentioned is Kolmogorov complexity. Some applications use the general notions of incompressible strings and prefix-free encoding wrt universal TMs while others can be more easily replaced by simple counting arguments that yield better results because they do not lose the constants inherent in the universal approach. The latter ones do not seem to be applications of the theory that justify its worth.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68620376127066093252008-05-12T12:19:00.000-05:002008-05-12T12:19:00.000-05:00There are two different reasons for including "app...There are two different reasons for including "applications" in theoretical publications:<BR/>(1) because the application is what you really want to solve, and the theory you're publishing really was useful for solving that application, and<BR/>(2) to convince program committees (or students) that the theory you're about to show them is worth reading or learning about because it's good for something they're more likely to already care about.<BR/><BR/>One might argue that applications of type (1) are better than applications of type (2), because they're more real and less just for show.<BR/><BR/>Of your three examples, I find the second and third to be better by this criterion than the first. There are other simpler ways of proving the fundamental theorem of algebra than by homotopy theory, so proving the FTA in this way is less about actually needing homotopy theory to prove it and more about showing off what homotopy theory is good for. On the other hand, the happy ending problem really was a historical motivation for the development of Ramsey theory, and Yao really couldn't find a better way at the time of proving his result about the cell probe model than to use Ramsey theory.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74270916646930642232008-05-12T12:10:00.000-05:002008-05-12T12:10:00.000-05:00Another pair of entries for the computational geom...Another pair of entries for the computational geometry section of your Ramsey applications page: http://arxiv.org/abs/math.CO/0109195 and http://arxiv.org/abs/math.CO/0204252Anonymousnoreply@blogger.com