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.
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.