That explains why we don't have widely implemented algorithms of higher-degree polynomial complexity, but it doesn't explain why we haven't thought of many such polynomial algorithms that just aren't practical. After all, we can easily name lots of super-exponential algorithms. They're not directly useful for even moderately sized data, but they arise naturally from looking at certain types of problems, so we almost can't help but find them. The same doesn't seem to be true for polynomial algorithms with high degree.
You're essentially referring to the idea that could be loads of high-order poly-time algorithms, but we ignore them because those algorithms are slow, and therefore we don't use them. So in the space of all useful algorithms, we simply have a very biased sample.
I think the truth is more profound than that. There actually don't exist very many interesting* algorithms in the classes O(n^(k>3)). The real world we live in and model does not feature many interesting problems for which high-order polynomial complexity algorithms are natural solutions.
*Not sure what the right word to use here is...maybe non-trivial? The point I'm going for is to say that obviously we can invent an O(n^5) algorithm by simply nesting our loops five-deep and printing something, but that's a constructed example. I'm looking for algorithms that naturally arise as a solution to some problem.
For example, there is 0.8776-approximation that runs in about O(n^{10^100}) https://arxiv.org/abs/1205.0458v2
There are also a lot of graph problems like "distinguish 3-colorable graph from graph that can't be colored in 3 colors even after removing eps part of edges" with large polynomials (IIRC, we got something like O(n^{2^40000}) when tried to find degree explicitly).
You're essentially referring to the idea that could be loads of high-order poly-time algorithms, but we ignore them because those algorithms are slow, and therefore we don't use them. So in the space of all useful algorithms, we simply have a very biased sample.
I think the truth is more profound than that. There actually don't exist very many interesting* algorithms in the classes O(n^(k>3)). The real world we live in and model does not feature many interesting problems for which high-order polynomial complexity algorithms are natural solutions.
*Not sure what the right word to use here is...maybe non-trivial? The point I'm going for is to say that obviously we can invent an O(n^5) algorithm by simply nesting our loops five-deep and printing something, but that's a constructed example. I'm looking for algorithms that naturally arise as a solution to some problem.