There are LOTS of np-hard problems that humans have “solved” numerically or partially for real-world uses, at scales that are economically important. They don’t scale perfectly, and they’re often not provably optimal, but they work.
These are part of the considerations I would address when I get around to writing the post.
Empirical probability distributions over inputs
Weighting problems by their economic importance
Approximate solutions
Probabilistic solutions
Etc.
All complicate the analysis (you’d probably want a framework for determining complexity that natively handled probabilistic/approximate solutions, so maybe input size in bits and “work done by optimisation in bits”), but even with all these considerations, you can still define a coherent notion of “time complexity”.
These are part of the considerations I would address when I get around to writing the post.
Empirical probability distributions over inputs
Weighting problems by their economic importance
Approximate solutions
Probabilistic solutions
Etc.
All complicate the analysis (you’d probably want a framework for determining complexity that natively handled probabilistic/approximate solutions, so maybe input size in bits and “work done by optimisation in bits”), but even with all these considerations, you can still define a coherent notion of “time complexity”.
Just messaged my lecturer, I’ll try and see if I can get permission for such a project.