Even when you get the direction correct-- e.g. that you could encode an arbitrary SAT problem as an instance of your problem... that doesn't mean that in practi

Even when you get the direction correct-- e.g. that you could encode an arbitrary SAT problem as an instance of your problem... that doesn't mean that in practice most instances of your problem can't be solved to an arbitrarily good approximation quickly or even solved optimally in a reasonable amount of time. It only means that in the worst case there is no efficient optimal solution or good approximation. I've repeatedly encountered people using crappy solutions to problems because they read some result from complexity theory that made them think they couldn't do better. .. when in reality a slightly smarter algorithm does much better on average. Consider for example the min cover problem: You have a set of bit vectors and you want to find the minimum collection where at least one vector is true for every bit. (e.g. optimizing a collection of tests). There is a simple greedy algorithm-- include the vector that covers the most yet-uncovered bits. There is a proof that this algorithm achieves the best possible worst case approximation error. But in practice this is a useless result. Worst case approximation error is driven by pathological inputs. It's easy to come up with modifications of the greedy algorithm that significantly improve the quality of the solutions on average (or at least do in the sorts of real problems I've applied it to).