= 27d567bc2d48d9f40e9ccc20ea370b15)
Lumifer comments on Computation complexity of AGI design - Less Wrong
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)
Intelligence doesn't operate on the basis of proving things. Intelligence operates on the basis of heuristics and so I find the parallel to NP-complete problems flawed.
For clarity, consider a human from 50,000 years ago and see if the way his intelligence operates has resemblance to solving problems in an NP-complete domain.
I don't quite follow your reasoning. Consider a Go-playing AI based on a Monte Carlo multi-armed bandit algorithm. A human player can analyze its moves and explain them from the point of view of regular human Go-theory. However this would reveal little about the inner operation of the algorithm.
Actual intelligence operates in the world of seriously incomplete data, fuzzy approximations, good-enough heuristics, and making a lot of mistakes. It is NOT the world of math proofs and hard analytical solutions.
So you're saying that complexity theory is useless in problems involve approximations, heuristics etc?
For one thing, there is a theory of approximate solutions and average case complexity as well. For another, the beauty of complexity theory is that it puts bounds on your abilities regardless of the methods you use: a complexity bound applies to any algorithm, whether analytical or heuristic.
No, I am not willing to make such a sweeping statement. However I will say that constraints and limitations that the hard complexity theory faces are not necessarily binding in the approximations/heuristics world.
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.