tag:blogger.com,1999:blog-3722233.post8868460092922532259..comments2020-05-27T23:17:32.309-04:00Comments on Computational Complexity: Fifty Years of Computational ComplexityLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-65001170143856486752012-11-16T15:27:52.432-05:002012-11-16T15:27:52.432-05:0050 shades of complexity theory. ;)50 shades of complexity theory. ;)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62416273071769400712012-11-13T18:33:24.413-05:002012-11-13T18:33:24.413-05:00A BibTeX entry for Hartmanis' monograph 1978 F...A BibTeX entry for Hartmanis' monograph 1978 <i>Feasible Computations and Provable Complexity Properties</i> might include these verbatim quotes:<br /><br />-------------<br />"It may be only a slight exaggeration to claim that in the 1930s we started to understand what is and is not effectively computatable and that in the 1970s we started to understand what is and is not practically or feasibly computable."<br /><br />"Results about the complexity of algorithms change quite radically if we consider only properties of computations which can be proven formally."<br /><br />"In the traditional view of complexity theory we consider all programs computing the same function as equivalent, though we have no way of verifying this; and we know that in any fixed formal function <i>F</i> many of these programs cannot be proven equivalent. Thus we should expect that the results about optimality of all programs computing the same function as a given program will differ from the optimality results about all programs which can be formally proven to be equivalent to the given program. The surprising thing is how much the classical optimization results differ from the optimization results for provably equivalent programs." <br /><br />"These results suggest very strongly that we need to explore further how our ``world view'' of the complexity of algorithms has to be changed if we consider only provable properties of algorithms."<br />------------<br /><br />What new insights has complexity theory evolved, in the decades since the 1970s, to match Hartman's still-fresh insights from the 1970s (along with Baker-Gill-Solovay, also from the 1970s)? John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5394059147275879942012-11-12T00:05:39.094-05:002012-11-12T00:05:39.094-05:00Didn't Lance declare the demise of complexity ...Didn't Lance <a href="http://blog.computationalcomplexity.org/2011/11/death-of-complexity-classes.html" rel="nofollow">declare</a> the demise of complexity classes almost a year ago from today? <br /><br />Unless I missed something no revival happened since then. In fact, looking at the recent abstracts in ECCC, we may as well rename the field to "informatics" or something like that.<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68620074760752311462012-11-11T12:32:01.951-05:002012-11-11T12:32:01.951-05:00A big big cheers from me to computational complexi...A big big cheers from me to computational complexity and the theoretical computer science community in the world.<br />Long live mankind, long live complexity theory.Arka Bhattacharyahttps://www.blogger.com/profile/00801802507777720869noreply@blogger.com