On the other hand note that we have conjectures which are stronger than P != NP which taken together do amount to saying that approximation can be tough and that many heuristics will also not be likely to succeed. P=BPP, and the Unique Games Conjecture can both be thought of as variations of that theme.
many heuristics will also not be likely to succeed.
Succeed in which sense? Take the traveling salesman problem. You can’t analytically solve it for N in the hundreds. But there are heuristics which give acceptable results and are widely used in practice.
Heuristics are not designed to get you to the optimum. They are, by definition, geared to produce a merely acceptable result.
Succeed in which sense? Take the traveling salesman problem. You can’t analytically solve it for N in the hundreds. But there are heuristics which give acceptable results and are widely used in practice.
It depends what you mean by acceptable. For many problems, assuming that P != NP, one cannot get approximations beyond a certain amount. In particular, one cannot get approximations which asymptotically approach the optimal. See for more details my earlier comment here.
On the other hand note that we have conjectures which are stronger than P != NP which taken together do amount to saying that approximation can be tough and that many heuristics will also not be likely to succeed. P=BPP, and the Unique Games Conjecture can both be thought of as variations of that theme.
Succeed in which sense? Take the traveling salesman problem. You can’t analytically solve it for N in the hundreds. But there are heuristics which give acceptable results and are widely used in practice.
Heuristics are not designed to get you to the optimum. They are, by definition, geared to produce a merely acceptable result.
It depends what you mean by acceptable. For many problems, assuming that P != NP, one cannot get approximations beyond a certain amount. In particular, one cannot get approximations which asymptotically approach the optimal. See for more details my earlier comment here.