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 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$greybeard– greybeard2020-08-23 07:26:13 +00:00Commented Aug 23, 2020 at 7:26
- $\begingroup$ @greybeard I didn't understand your question. $\endgroup$plop– plop2020-08-23 09:57:36 +00:00Commented Aug 23, 2020 at 9:57
- $\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$2020-08-24 00:16:32 +00:00Commented 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$plop– plop2020-08-24 00:23:27 +00:00Commented Aug 24, 2020 at 0:23
[primality test] considered to be not in P? $\endgroup$