> Also, there exist problems that are NP hard that cannot be solved in polynomial time and have atrocious worst-case complexity, but their average complexity is

> Also, there exist problems that are NP hard that cannot be solved in polynomial time and have atrocious worst-case complexity, but their average complexity is quite reasonable and feasible for a machine to calculate. This is an active research topic of trying to characterize worst-case assumptions (i.e., the traditional kind) that imply average-case hardness for some problems, with several recent exciting results. See, for instance, an excellent talk here: https://www.youtube.com/watch?v=aQZEsmpbWE0&t=578s https://www.youtube.com/watch?v=aQZEsmpbWE0&t=578s