28

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.)

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Vincenzo
  • 751
  • 6
  • 11
  • 1
    +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]$? – Kaveh Feb 12 '11 at 18:55
  • @Kaveh: Three fingers pointing back at me, I guess. We should set up a policy forbidding answers in comments ;) – Hsien-Chih Chang 張顯之 Feb 12 '11 at 19:50

2 Answers2

23

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.

http://michaelnielsen.org/polymath1/index.php?title=Finding_primes

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.

http://polymathprojects.org/2010/06/29/draft-version-of-polymath4-paper/

Cong Han
  • 566
  • 1
  • 5
  • 9
14

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.

Hsien-Chih Chang 張顯之
  • 7,638
  • 4
  • 44
  • 83
  • 1
    I'm curious as to how standard Cramér's conjecture is. I was under the impression that the odds were against it. – Cong Han Feb 13 '11 at 23:15
  • @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'. – Hsien-Chih Chang 張顯之 Feb 14 '11 at 02:24
  • @ 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: http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer.pdf – Cong Han Feb 14 '11 at 05:23
  • @Cong: Seems like a nice reading, I'll go through it in a few days! – Hsien-Chih Chang 張顯之 Feb 14 '11 at 05:50