tag:blogger.com,1999:blog-3722233.post8074027353717692435..comments2023-03-20T21:49:52.361-05:00Comments on Computational Complexity: What was the first result in complexity theory?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-91138619746025342412017-02-03T22:58:54.235-06:002017-02-03T22:58:54.235-06:00You can find older examples in analysis.You can find older examples in analysis.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74618667428142819082017-02-01T11:48:02.787-06:002017-02-01T11:48:02.787-06:00This may not fit your definition, but there's ...This may not fit your definition, but there's Shannon's 1949 proof that most Boolean functions need exponentially-large circuits to compute. (Scott Aaronson's recent P?=NP survey describes it nicely.) It does have the <i>large</i> weakness that it doesn't tell you <i>any</i> function which requires large circuits... On the other hand, it is from the vacuum-tube era, which arguably makes it more noteworthy.<br />Josh Burdickhttps://www.blogger.com/profile/12231348292069164630noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3827532980630489332017-01-31T07:38:54.261-06:002017-01-31T07:38:54.261-06:00Gabriel Lame's bounds on the Euclidean algorit...Gabriel Lame's bounds on the Euclidean algorithm.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62723355428909429522017-01-31T06:53:36.328-06:002017-01-31T06:53:36.328-06:00Yes. I sometimes teach the Discrete Math class and...Yes. I sometimes teach the Discrete Math class and I always keep track of whats going on in it. <br /><br />And yes, Countability and Uncountability seems to be the hardest topic in it by half an order of magnitude. That might be a reason to take it out of the course, or not. (A later post might be on what should be in a DM course, or might not.)GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87902283163077972662017-01-30T19:52:21.125-06:002017-01-30T19:52:21.125-06:00are you sure they show that to freshmen in the dis...are you sure they show that to freshmen in the discrete math class there?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48245145116525546852017-01-30T06:41:28.411-06:002017-01-30T06:41:28.411-06:00Candidate: the Ackermann function is not primitive...Candidate: the Ackermann function is not primitive recursive.Jan Johannsenhttps://www.blogger.com/profile/16124485013953473170noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66420935783111568962017-01-30T03:51:50.828-06:002017-01-30T03:51:50.828-06:00For me the main difference between computability a...For me the main difference between computability and complexity is that the former is qualitative (one cannot compute something at all in the considered model) whereas the latter is quantitative (you can compute something and it will take you a certain amount of resources, e.g. time size memory, ...).<br /><br />With this working definition, your questions 1) to 4) are not complexity questions whereas the others are.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55269076447100925842017-01-30T01:57:09.909-06:002017-01-30T01:57:09.909-06:00Kleene's Theorem characterizes constant space....Kleene's Theorem characterizes constant space.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5277147329184239082017-01-30T01:23:24.012-06:002017-01-30T01:23:24.012-06:00Without the Cook-Levin theorem, there is no comple...Without the Cook-Levin theorem, there is no complexity theory.<br /><br />Rafee Kamouna.Rafee Kamounahttps://www.blogger.com/profile/12584274746853342694noreply@blogger.com