# Why AKS primality test is called polynomial?

It's complexity is $\mathcal{O}(\log^6n)$ and $\log^6n$ is not a polynomial. Can we say that primality testing is strictly contained in $P$ then?

• When you say strictly in P, are you referring to a lower-bound on the time complexity? – jmite May 18 '17 at 20:20

The time complexity of the AKS primality test is $O(n^6)$, where $n$ is the length of the input. The length of an integer $N$ is roughly $\log N$, so the time complexity of the AKS primality test applied to the integer $N$ is $O(\log^6 N)$.
Finally, I'm not sure what you mean by a problem being strictly contained in P. Every problem in P is contained in some smaller class $\mathsf{TIME}(O(n^k))$ for some $k$.
• By "strictly contained" I meant that if a task can be solved in $\mathcal{O}(log^kn)$ time then by time hierarchy theorem it's strictly contained in $P$. But this doesn't make sence here, cause of difference between $N$ and $n$. – rus9384 May 18 '17 at 14:23
Any function which is $O(\log^k n)$ for any constant $k$ is $O(n)$. The concept of "strictly contained" doesn't really make sense. Properly speaking, the statement is that primality is an element of the set of problems that can be decided in polynomial time. There's no such thing as "strictly an element": something is either an element or it isn't.
• The point is that $n$ is the number tested for primality, and the algorithm is ("strictly") polynomial in the length of the number, which is $\log n$. – Yuval Filmus May 18 '17 at 14:24