We All Guessed Wrong « Gödel’s Lost Letter and P=NP
Neil Immerman and Robert Szelepcsenyi are two computer scientists who are famous for solving a long standing open problem. What is interesting is that they solved the problem at the same time, in 1987, and with essentially the same method. Independently. Theory is like that sometimes.
Robert was a student when he solved the problem. The legend is that he was given a list of homework problems. Since he missed class he did not know that the last problem of his homework was the famous unsolved LBA question. He turned in a solution to the homework that solved all the problems. I cannot imagine what the instructor thought when he saw the solution.Posted on 2011-05-08T18:32:46+0000