The basic answer is, computational complexity matters less than you think, primarily because it makes very strong assumptions, and even one of those assumptions failing weakens it’s power.
The assumptions are:
Worst case scenarios. In this setting, everything matters, so anything that scales badly will impact the overall problem.
Exactly optimal, deterministic solutions are required.
You have only one shot to solve the problem.
Small advantages do not compound into big advantages.
Linear returns are the best you can do.
This is a conjunctive argument, where if one of the premises are wrong, than the entire argument gets weaker.
And given the conjunction fallacy, we should be wary of accepting such a story.
The basic answer is, computational complexity matters less than you think, primarily because it makes very strong assumptions, and even one of those assumptions failing weakens it’s power.
The assumptions are:
Worst case scenarios. In this setting, everything matters, so anything that scales badly will impact the overall problem.
Exactly optimal, deterministic solutions are required.
You have only one shot to solve the problem.
Small advantages do not compound into big advantages.
Linear returns are the best you can do.
This is a conjunctive argument, where if one of the premises are wrong, than the entire argument gets weaker.
And given the conjunction fallacy, we should be wary of accepting such a story.
Link to more resources here:
https://www.gwern.net/Complexity-vs-AI#complexity-caveats