Is a deterministic polynomial-time algorithm known for the following problem:

Input: a natural number $n$ (in binary encoding)

Output: a prime number $p > n$.

(According to a list of open problems by Leonard Adleman, the problem was open in 1995.)

  • 1
    $\begingroup$ +1: It reminded me that the corresponding natural decision problem is not primality testing (which is in $\mathbf{P}$) but rather the following problem: given $a<b$, is there a prime number in the interval $[a,b]$? $\endgroup$ – Kaveh Feb 12 '11 at 18:55
  • $\begingroup$ @Kaveh: Three fingers pointing back at me, I guess. We should set up a policy forbidding answers in comments ;) $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 12 '11 at 19:50

The current best unconditional result was given by Odlyzko, which finds a prime $p >N$ in $O(N^{1/2 + o(1)})$ time. The strong conjecture in Polymath4 project seeks to resolve if this can be done in polynomial time, under reasonable number-theoretic assumptions like the GRH.


Currently the project seeks to answer the following question:

Given a number $N$ and an interval between $N$ and $2N$, check in time $O(N^{1/2 - c})$ for some $c>0$ if the interval contains a prime.

So far, they have a strategy which determines the parity of the number of primes in the interval.


| cite | improve this answer | |

Assuming standard conjecture in number theory, which states that

Cramér's conjecture: Let $p_n$ be the n-th prime. Then $p_{n+1}-p_n = O(\log^2 p_n)$.

We have a deterministic polynomial-time algorithm for the problem, simply by running primality test on each number larger than $n$ start from $n+1$. (Of course, $n$ should be large enough; for small $n$ we treated separately.)

But I'm not sure this can be proved unconditionally.

| cite | improve this answer | |
  • 1
    $\begingroup$ I'm curious as to how standard Cramér's conjecture is. I was under the impression that the odds were against it. $\endgroup$ – Cong Han Feb 13 '11 at 23:15
  • $\begingroup$ @Cong: I'm not really familiar with the conjecture, and my impression is that we have evidences in numerical results and also it holds in the random model. Is there any indication that the conjecture might be false? Maybe I should state 'strong' instead of 'standard'. $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 14 '11 at 2:24
  • $\begingroup$ @ Hsien-Chih: I know very little about this (besides some hearsay and having a passing interest in the Polymath projects), but this article by Granville, linked from the wiki on the conjecture, seems to suggest so: dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/… $\endgroup$ – Cong Han Feb 14 '11 at 5:23
  • $\begingroup$ @Cong: Seems like a nice reading, I'll go through it in a few days! $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 14 '11 at 5:50

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.