4
$\begingroup$

To check if $n$ is prime, one only need to try dividing $n$ by numbers up to $\sqrt{n}$, meaning that the complexity would be $O(\sqrt{n})$. In my opinion, $O(\sqrt{n}) < O(n)$ so this simple algorithm is already P. But why did people think that primality test is NP, and were surprised by the AKS primality test?

$\endgroup$

marked as duplicate by David Richerby, Evil, xskxzr, Discrete lizard Apr 27 at 17:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 8
    $\begingroup$ If something is in P then it is automatically in NP. You seem to be using "NP" as shorthand for either "NP - P" or "NP-complete". $\endgroup$ – John Coleman Apr 27 at 11:28
  • $\begingroup$ And I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP. Then it was shown to be in NP and co-NP, which was odd. Many people believed it was "slightly" exponential. $\endgroup$ – gnasher729 Apr 27 at 13:48
5
$\begingroup$

To start, any decision problem with a witness verifiable for a "yes" answer in polynomial time is in NP.

$\bullet$ The problem 'Is $p$ composite?' has a witness $k$, and it can be tested in polynomial time whether $k$ divides $p$, therefore is in NP.

$\bullet$ The problem 'Is $p$ prime?' has a polynomial certificate (which can be found here), therefore is also in NP.

Now, your complexity analysis is not correct. If your input is a number $p$, then the input size is $\log (p)$, since you need $log(p)$ bits to represent it. Therefore, $n=\log(p)$ and $\sqrt{p}=\frac{1}{2} \log(p)$ bits. So the time required (in respect to $n$) checking all the numbers up to $\sqrt{p}$ will be $2^{\frac{1}{2}n}$, and is in fact exponential in terms of input size $n$.


The question "Where exactly does the Primality problem lie" has been answered in the link here

$\endgroup$
  • 1
    $\begingroup$ "Is p composite" is obviously in NP, because you can bring a witness easily. "Is p prime" is in NP, but not obviously at all - there is a quite deep theorem that every prime p has a short prove of being prime, which I think involves complete factorisations of p+1 and/or p-1. $\endgroup$ – gnasher729 Apr 27 at 11:05
  • $\begingroup$ @gnasher729 thank you for spotting it! I edited it in. $\endgroup$ – lox Apr 27 at 11:56
0
$\begingroup$

I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP (which is required for NP-complete). Then it was shown to be in NP and co-NP, which was odd.

And you could of course do probabilistic tests in polynomial time. It is quite likely that there is a not very large polynomial p(n) so that doing p(n) probabilistic tests proves indeed that a number of size n is a prime. In which case primality was always in P. (It's just hard to prove).

$\endgroup$

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