It's worth noting this cuts both ways. An NP-complete problem may wind-up having only a few instances that are exponential in the inputs but a problem that is "only" O(input-size^3) is going to be difficult to deal for input of significant size.
It's worth noting this cuts both ways. An NP-complete problem may wind-up having only a few instances that are exponential in the inputs but a problem that is "only" O(input-size^3) is going to be difficult to deal for input of significant size.
It is indeed very interesting. For the latter the concepts from fine-grained complexity and average time are interesting. For specific problems, there are theoretical fine grained lower bounds for time complexity (i.e. cannot be solved in (truly) subcubic time). However, these rely on assumptions that are even stronger than P != NP.
Like matrix multiplication! That's N^3 naively. If you take N to be the size of each dimension.