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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ When you say strictly in P, are you referring to a lower-bound on the time complexity? $\endgroup$– jmiteMay 18, 2017 at 20:20
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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$.
answered May 18, 2017 at 14:12
-
$\begingroup$ 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$. $\endgroup$– rus9384May 18, 2017 at 14:23
-
2$\begingroup$ @rus9384 A task is either in P or it isn't. There's still no such thing as an element being "strictly in" a set. $\endgroup$ May 18, 2017 at 15:03
$\begingroup$
$\endgroup$
2
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.
answered May 18, 2017 at 14:13
-
$\begingroup$ 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$. $\endgroup$ May 18, 2017 at 14:24
-
$\begingroup$ @YuvalFilmus That's true, though there are several misunderstandings in the question and I pointed out the ones that don't require remembering what the actual complexity of the AKS algorithm is. :-) $\endgroup$ May 18, 2017 at 15:03