= 27d567bc2d48d9f40e9ccc20ea370b15)
JoshuaZ comments on Computation complexity of AGI design - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (69)
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.