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?