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

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 http://www.kmjn.org/notes/nphard_not_always_hard.html