1
$\begingroup$

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.

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

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ (While $O(n)$ looks as true as $\in\mathbb P$, can you quote (and argue) a tighter bound?) $\endgroup$
    – greybeard
    Aug 23, 2020 at 7:26
  • $\begingroup$ @greybeard I didn't understand your question. $\endgroup$
    – plop
    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$
    – 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$
    – plop
    Aug 24, 2020 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.