tag:blogger.com,1999:blog-3722233.post1089259264069064..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: RESULTAPHOBIA!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-1089453964810686352004-07-10T05:06:00.000-05:002004-07-10T05:06:00.000-05:00I have a question, the text notes "the absurd resu...I have a question, the text notes "the absurd result that ?1-SPACE(n)=?1=SPACE(n)." Am I to assume that the implication is that the "absurd result" is actually true? I am not aware of the class ?1-SPACE(n). Thanks. :-)Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1089284861363311122004-07-08T06:07:00.000-05:002004-07-08T06:07:00.000-05:00It's great to read stories like this, because ther...It's great to read stories like this, because there are urban legends floating around about the very same theme: A student comes to class late and writes down 10 problems from the board, believing it was homework. The student turns in solutions for a fair number of problems, not knowing the list was open problems in the field. Either way, it's a great story.<br /><br />It makes me think back to an Alan Kay quote where the work at PARC on Smalltalk is described as nothing short of amazing and Kay replied "we didn't know it was hard."Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1089262929215571942004-07-08T00:02:00.000-05:002004-07-08T00:02:00.000-05:00Sorry for anonymous post, A famous example is Huff...Sorry for anonymous post, A famous example is Huffman code, once I read an interview with huffman, seemingly he has been an undergrad student in a course taught by Shannon. Shannon says in the class that whoever finds the optimum code would receive full mark in the course (or another great prize) but he didn't mentioned that the problem is open. Huffman solved it and won the prize!Anonymousnoreply@blogger.com