Exact Exponential Algorithms

Like learning about the physics of the very large and very small, the study of computational extremes will change your intuitive sense of the laws governing the universe -- especially if you are a working programmer and used to interacting primarily with tractable problems.<p>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. And by the end of the class, you will no longer laugh at that joke." He went on to show us the Halting Problem (an impossible-to-solve problem), then problems that one still can't solve <i>even given an oracle for the halting problem</i>. In other words: even if you <i>could</i> solve the Halting Problem, you <i>still</i> couldn't solve these other problems. And even if you <i>could</i> solve some of those problems, there are others you still couldn't solve, etc. Ultimately, we learned about Recursion Theory, which examines this implied infinite hierarchy of "impossibility".<p>Another interesting -- and, really, somewhat devastating -- conclusion one can draw from Recursion Theory is that tractable problems are incredibly rare. From a cardinality standpoint, the set of solvable problems is vanishingly small compared to the universe of unsolvable problems. It just so happens that many problems we actually care about are solvable and tractable. But, numerically speaking, this is incredibly unlikely. (In other words, if the distribution of problems we cared about were actually uniform, we'd be able to solve basically nothing we cared about.)<p>Exact exponential algorithms -- those "right at the edge of tractability" -- open one's eyes in similar ways. Why do we end up with magic numbers x, where the known lower bound seems to be O(x^n) where 1 &#60; x &#60; 2? Will we find underlying mathematical constants here that we don't yet know about? I think every day working developers would do well to learn about these tractability "edge cases".

This is very much a theoretical perspective. If you have to solve an NP-complete problem in practice, you wouldn't use any of the algorithms described in this article, you'd use a DPLL based SAT solver. A modern SAT solver will be orders of magnitude faster than these algorithms for practical cases. There is an international SAT solver competition every two years where you can find the current winning SAT solver: <a href="http://www.satcompetition.org/" rel="nofollow">http://www.satcompetition.org/</a>

Annex - this rather illuminant book :<p><a href="http://www.nature-of-computation.org" rel="nofollow">http://www.nature-of-computation.org</a>