tag:blogger.com,1999:blog-3722233.post113356134523307029..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: Complexity in the Mid-80'sLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-1133712935350841232005-12-04T10:15:00.000-06:002005-12-04T10:15:00.000-06:00The main thing is that it would have to include Ra...The main thing is that it would have to include Razborov-Rudich's natural proofs paper.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133660057452256262005-12-03T19:34:00.000-06:002005-12-03T19:34:00.000-06:00Today it seems that at best such a course might en...Today it seems that at best such a course might end with an approach to separate #P from ACC^0.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133644951520276152005-12-03T15:22:00.000-06:002005-12-03T15:22:00.000-06:00More accurately in this regard, very little has ch...More accurately in this regard, very little has changed in the last 20 years.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133636601305497372005-12-03T13:03:00.000-06:002005-12-03T13:03:00.000-06:00"Much of this course revolved around the isomorphi..."Much of this course revolved around the isomorphism conjecture that Hartmanis felt at the time could lead to a proof that P ? NP."<BR/><BR/>"Sipser ended the course talking about his approach to showing NP ? co-NP"<BR/><BR/>Things surely have changed in 20 years.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133569788358155842005-12-02T18:29:00.000-06:002005-12-02T18:29:00.000-06:00I started graduate school at Berkeley but when Sip...I started graduate school at Berkeley but when Sipser, my advisor, moved back to MIT in the summer of '86, I followed.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133567461034621142005-12-02T17:51:00.000-06:002005-12-02T17:51:00.000-06:00UC Berkeley? I thought you attendedMIT for grad sc...UC Berkeley? I thought you attended<BR/>MIT for grad school.Anonymousnoreply@blogger.com