While a basic algorithm to check for primality of a number 'n' [checking if a divides n for all a less than n] would take O(n), AKS test was the breakthrough after which it was placed in P complexity class.
1
1 Answer
$\begingroup$
$\endgroup$
4
The bit length of $n$ is $\log(n)$, if we forget about the most significant digits, which is always $1$ except for $n=0$. As a function of $t=\log(n)$ you have $n^{1/2}=2^{t/2}$. It is in terms of the bit length of $n$ that AKS runs in polynomial time, while the naive test doesn't.
-
$\begingroup$ (While $O(n)$ looks as true as $\in\mathbb P$, can you quote (and argue) a tighter bound?) $\endgroup$ Aug 23, 2020 at 7:26
-
-
$\begingroup$ What a lot of people seem to miss is that P and NP are defined in terms of Turing machines. A problem is in P if the TM takes at most a polynomial number of steps $p(n)$ where $n$ is the number of symbols on the input tape. $\endgroup$– Pseudonym ♦Aug 24, 2020 at 0:16
-
$\begingroup$ @Pseudonym They had a different problem, which is how $n$ is input. If $n$ is input in unary in the Turing machine, then the naive algorithm would be polynomial. $\endgroup$– plopAug 24, 2020 at 0:23
[primality test] considered to be not in P? $\endgroup$