1
$\begingroup$

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?

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

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$.

$\endgroup$
  • $\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$ – rus9384 May 18 '17 at 14:23
  • 1
    $\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$ – David Richerby May 18 '17 at 15:03
1
$\begingroup$

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.

$\endgroup$
  • $\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$ – Yuval Filmus May 18 '17 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$ – David Richerby May 18 '17 at 15:03

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.