Examples of high polynomial order complexity

Question

I was reading Twenty Questions for Donald Knuth and was intrigued by Knuth's argument in question 17 for why he suspects P=NP. In the discussion he asks why you couldn't have an algorithm bounded by a finite but incredibly large polynomial order.

I am not a computer scientist, but I don't know of any really high-order polynomial algorithms. I know of a few from computational physics that are bounded by $N^{12}$, and, based on those, I can imagine that there are some that are like $N^{20}$. But I can't think of any useful algorithms that would be, say, $\mathcal{O}(N^{1000})$.

By useful, I mean based on something I would actually want to do, solving some problem from physics or something, not something dreamed up for the sake of creating a high-polynomial-order algorithm. Can someone give me a few examples of real problems with high polynomial order?

Answer 1

A thread on cstheory has a few examples. So, there are definitely algorithms with very high exponents that were made for purposes other than simply creating a high-polynomial-order algorithm.

However, the tricky bit is that for any high-order algorithm to be useful, $N$ has to be really really small. In physics, I don't know of any high order polynomial algorithms.

Going to a worse case than polynomial, quantum simulations are exponential in the number of particles simulated. This is why chemistry simulations tend to be a mix of classical and quantum simulations. We simply don't have the machine power to simulate molecular interactions quantum mechanically.