Hacker News new | past | comments | ask | show | jobs | submit login
Exact Exponential Algorithms (acm.org)
57 points by Hitchhiker on March 18, 2013 | hide | past | favorite | 4 comments



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.

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 even given an oracle for the halting problem. In other words: even if you could solve the Halting Problem, you still couldn't solve these other problems. And even if you could 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".

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.)

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 < x < 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: http://www.satcompetition.org/


That's true, the heuristic approach is the one that's been more successful in practice. I think it can still be interesting (even if only theoretically) whether an non-approximation algorithm with worst-case running time guaranteed better than brute-force is possible for a given problem. There might even be some practical applications of having a guaranteed running time.

Nonetheless I would use the heuristic approach on most problems. And it's a little misleading when texts like the one linked here emphasize the need for "exact" solutions over those given by approximation algorithms, when heuristic algorithms also give exact solutions (just not with any particular guaranteed worst-case running time, which is a different issue from exactness).

Some of the issue, I think, comes from the fact that these classes of problems may be too "big" and heterogenous: we say that "SAT" is NP-complete, but it's only really a subset of SAT problems that are hard, amidst huge swathes of trivial SAT problems. Heuristic approaches are just very good at finding those, which happen to be quite common in a lot of real-world situations. If you narrowed it down to some kind of "hard SAT" (like the research on "phase-change" SAT problems is trying to do), then these algorithms may have more of a reason for existence, because you've pruned out all the stuff heuristics can solve well, leaving only the still-hard stuff. That feature, that NP-complete problems, without further restriction, typically have a lot of instances that are easily heuristically solvable, is also a main reason NP-complete problems haven't been historically successful as a building block for crypto [1].

[1] http://www.kmjn.org/notes/nphard_not_always_hard.html


Annex - this rather illuminant book :

http://www.nature-of-computation.org




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: