Exact Exponential Algorithms
Many computational problems have been shown to be intractable, either in the strong sense that no algorithm exists at all—the canonical example being the undecidability of the Halting Problem—or that no efficient algorithm exists. From a theoretical perspective perhaps the most intriguing case occur...
Hasnain says:
|At U Maryland I took a course from Bill Gasarch on computation. The first thing he said to the class, famously, was "I'm going to show you that there are problems that are impossible to solve. Then I'm going to show you some problems even harder than those.""
This is a good read.
Posted on 2013-03-18T12:47:33+0000