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.

  • $\begingroup$ Can you give a reference or proof for [primality test] considered to be not in P? $\endgroup$ – greybeard Aug 23 '20 at 7:22

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 Aug 23 '20 at 7:26
  • $\begingroup$ @greybeard I didn't understand your question. $\endgroup$ – plop Aug 23 '20 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$ – Pseudonym Aug 24 '20 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 Aug 24 '20 at 0:23

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.