[btilly]

True, there are lots of cases where an approximation can create provably good answers question. But they usually require things like having probabilities bounded away from 1 and 0.

Unfortunately in the real world we actually are certain about lots of things. And when you add data, we tend to be more certain of previously uncertain things. Therefore we wind up with self-referential networks of beliefs that reinforce each other.

But sometimes there are two very different networks of beliefs, both of which are self-reinforcing. And a single data point can flip between them. Identifying which one is computationally impossible. However when you encounter someone whose beliefs are very different, and you can find the feedback loops that draw each of you in different directions, there is a good chance that the differences between you cannot be resolved by pure logic alone.

[FreakLegion]

I mean cases where the approximation isn't provably (or at least proven) good, but is still good in practice. This isn't uncommon with NP-hard problems or algorithms with bad worst-case behavior more generally, e.g. the Horspool variant of Boyer-Moore, or PCRE. It only takes one pathological case to wreck your guarantees, but those cases may be rare or even nonexistent in the real world.

Of course you actually could prove better bounds for an approximation algorithm given a specific universe of inputs. Your 'probabilities bounded away from 1 and 0' sound like an example of that (presumably the 'special cases' from the Bayesian network reference, but I only read the abstract). What I see more often are empirical studies showing, say, > 98% optimality for some kind of max cover approach to a specific problem, even though the guarantee in general is < 64%.