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