tag:blogger.com,1999:blog-3722233.post8322009766625865132..comments2022-08-09T23:53:51.029-05:00Comments on Computational Complexity: Fiftieth Anniversary of the Publication of the seminal paper on Computational ComplexityLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-78492788425727432982015-05-15T01:40:05.603-05:002015-05-15T01:40:05.603-05:00I talked to Hartmanis about this in 2012 and asked...I talked to Hartmanis about this in 2012 and asked if they had considered using recursive function theory. He said they had and it had made things horribly complicated. Then they came across Turing machines and the whole thing became 'so simple' !Mathaihttps://www.blogger.com/profile/15707971403272056315noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63466117696590228122015-05-14T16:43:08.426-05:002015-05-14T16:43:08.426-05:00People did study interesting subclasses of computa...People did study interesting subclasses of computable functions. The approach was definitional, rather than "use of resources". I believe that the Hartmanis and Stearns approach was the first that counted steps (and memory).<br />Other important precursors include Rabin (who tried to define "f is harder than compute than g", and discussed, essentially, one-way functions for cryptography;<br />Cobham, who wanted to formalize the notion "it is harder to multiply than to add",<br />and Edmonds, who needed to define the class P to justify why his polynomial time algorithm for non-bipartite matching was a good thing, even though it was too slow for the computers that there were around. [Of course, this is an oversimplified account!]<br />In any case, Hartmanis and Stearns was explicit, well argued, well written, and for all practical purposes, THE paper that launched Complexity.CSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65416463320690132242015-05-14T14:11:14.242-05:002015-05-14T14:11:14.242-05:00Were earlier complexity classes like e.g. Primitiv...Were earlier complexity classes like e.g. Primitive Recursive functions ever considered as being motivated by "reasonable runtimes"? Obviously they weren't that, but was that an aim? It's just kind of hard to imagine computability theory operating for like 30 years without any kind of complexity theory existing.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71262987761371924072015-05-14T09:24:15.317-05:002015-05-14T09:24:15.317-05:00Great picture. Love the haircuts. Great picture. Love the haircuts. Fashionable complexity theoristhttp://nanoreply@blogger.com