= 27d567bc2d48d9f40e9ccc20ea370b15)
Lumifer 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)
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.