[Solved]: Is determining if there is a prime in an interval known to be in P or NP-complete?

Problem Detail: 

I saw from this post on stackoverflow that there are some relatively fast algorithms for sieving an interval of numbers to see if there is a prime in that interval. However, does this mean that the overall decision problem of: (Does there exists a prime in an interval?) is in P. (There were a lot of answers to that post that I did not read so I apologize if this question is a duplicate or unnecessary).

On the one hand, if the interval is large enough (for example $[N,2N]$) then something like Bertrand's Postulate applies and there is definitely a prime in this interval. However, I also know that there are arbitrarily large gaps between two primes (for example $[N!,N!+ N]$.

Even if the decision problem is in P I don't see how the corresponding search problem is also tractable because, then we may not be able to draw on the same properties regarding the known distribution of primes when performing binary search.

Asked By : Ari

Answered By : D.W.

So your problem is as follows:

Input: integers $\ell,u$
Question: does there exist a prime in $[\ell,u]$?

As far as I know, it is not known whether that problem is in P or not.

Here's what I do know:

• Primality testing (given a single number, test whether it is prime) is in P, so if the range is small enough, you can exhaustively test each number in the range to see whether it is prime -- but this does not lead to a general algorithm.

• If Cramer's conjecture is true, then the problem is in P. Cramer's conjecture says that the gap between consecutive primes near $n$ is $O((\log n)^2)$, so the following algorithm will be in P: iterate through the numbers $\ell,\ell+1,\ell+2,\ell+3,\dots$, testing each whether it is prime; if you find one that is prime, stop immediately with a yes answer; if you hit $u$, stop with a no answer. Cramer's conjecture tells us that you'll stop after most $O((\log \ell)^2)$ primality-tests, so that algorithm will run in polynomial time.

  Unfortunately, the known results on prime gaps don't seem strong enough to prove unconditionally that the problem is in P.

• Here is another simple algorithm: repeatedly pick a random integer $r$ from $[\ell,u]$, and test whether it is prime. Stop if you find a prime, or if you've tried every integer in $[\ell,u]$ and none were prime. Heuristically, we should expect this to be efficient in practice. The prime number theorem tells us that if you randomly choose number in the vicinity of $u$, the probability it is prime will be about $1/\log n$. Thus, heuristically, we should expect that after about $O(\log u)$ iterations, you'll typically find a prime and stop, if one exists. On the other hand, due to the coupon collector's problem, if there is no prime in the range $[\ell,u]$, you'll stop after about $O((u-l) \log(u-l))$ iterations. So, if we had a good upper bound on the size of the longest gap between prime numbers, this would imply that the problem is in BPP. Even without such an upper bound, it follows that random problem instances are easy.

• Probably one can apply sieving methods to improve the running time in practice (e.g., to avoid doing any primality testing on numbers that are divisible by a small prime). I don't know whether this can be shown to lead to any asymptotic improvement.

• Due to these techniques, the problem is probably easy in practice.

• Due to the above remarks, I personally doubt that the problem is NP-complete.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45456