# Examples of high polynomial order complexity

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?

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.
• BTW, there is an example on the page @LKlevin linked to that has an approximation to Max Bisection that is order $10^{10^{100}}$. Badass! – Rick Jun 1 '14 at 0:11