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