Hacker News Reader

Comment by sidmitra | Hacker News Reader

I think it would make things more interesting. So many problems that would then be solvable in polynomial time.

Recall that primality testing was proved to be in P, O(n^6) via the AKS primality test, but in practice it's much too slow. So if something interesting is in P, but it's O(n^100), what good is that?

http://en.wikipedia.org/wiki/AKS_primality_test

well, it just brings us a couple of steps closer to an answer for "life, universe and everything"! :-)

Isn't it O(log n)? I guess computationally it may blow up if you are doing a significant number of operations.

It depends on how you measure n. The O(log^{6+\epsilon}(n)) quote on Wikipedia is for n being the number to be tested. This is "cheating"; inputs to an algorithm need to be measured by their length, and numbers are exponential in their length (i.e., the length of the number n is order log n for "reasonable encodings").

As an example, the knapsack problem with n objects and weight W is solvable in O(n*W) time, but it's known to be NP-hard. This doesn't prove P=NP, because W is exponential in its length. This is called a pseudopolynomial algorithm.

Ah got it. Thanks for the clarification.

Coincidental too since I just read about the AKS algorithm on Terrence Tao's blog. http://terrytao.wordpress.com/2009/08/11/the-aks-primality-t...

You could potentially use a run (or runs) through the O(n^100) problem to optimize approaches for smaller problems. If you were lucky that would ammortize the cost of the first run.

With a bit of luck you might also be able to come up with a scheme to generate optimal nonuniform circuits for smaller problem sizes, which would ammortize nicely if you had enough of the smaller instances to solve.

Reply on news.ycombinator.com