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?


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.

  • $\begingroup$ Actually, quantum is my field, and I know of lots of exponential algorithms. But thanks for the link. $\endgroup$
    – Rick
    May 31 '14 at 23:41
  • $\begingroup$ 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! $\endgroup$
    – Rick
    Jun 1 '14 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.