<p>Assuming <a href="http://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture">standard conjecture</a> in number theory, which states that</p>

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

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

<p>But I'm not sure this can be proved unconditionally.</p>

CC BY-SA 2.5
2011-02-13T23:15:14.390Z
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
CC BY-SA 2.5
2011-02-14T02:24:55.033Z
@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 張顯之
CC BY-SA 2.5
2011-02-14T05:23:17.767Z
@ 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
CC BY-SA 2.5
2011-02-14T05:50:54.570Z
@Cong: Seems like a nice reading, I'll go through it in a few days!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-12T19:46:10.410Z
2011-02-12T19:46:10.410Z
Hsien-Chih Chang 張顯之
<p>The current best unconditional result was given by Odlyzko,  which finds a prime $p &gt;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. </p>

<p><a href="http://michaelnielsen.org/polymath1/index.php?title=Finding_primes">http://michaelnielsen.org/polymath1/index.php?title=Finding_primes</a></p>

<p>Currently the project seeks to answer the following question:</p>

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

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

<p><a href="http://polymathprojects.org/2010/06/29/draft-version-of-polymath4-paper/">http://polymathprojects.org/2010/06/29/draft-version-of-polymath4-paper/</a></p>

CC BY-SA 2.5
2011-02-12T18:30:42.560Z
2011-02-12T18:30:42.560Z
Cong Han
<p>Is a <em>deterministic</em> polynomial-time algorithm known for the following problem: </p>

<p>Input: a natural number $n$ (in binary encoding)</p>

<p>Output: a prime number $p &gt; n$. </p>

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

CC BY-SA 2.5
2011-02-12T18:55:31.617Z
+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
CC BY-SA 2.5
2011-02-12T19:50:43.593Z
@Kaveh: Three fingers pointing back at me, I guess. We should set up a policy forbidding answers in comments ;)
Hsien-Chih Chang 張顯之
<cc.complexity-theory><open-problem><nt.number-theory><polynomial-time><primes>
Finding a prime greater than a given bound
Vincenzo
# Finding a prime greater than a given bound

(Asked by: username_0 on 2011-02-12)

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

**Tags:** cc.complexity-theory, open-problem, nt.number-theory, polynomial-time, primes
> **Comments:**
> **username_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]$?  
> **username_2**: @Kaveh: Three fingers pointing back at me, I guess. We should set up a policy forbidding answers in comments ;)  

---

## 2 answers

### Answer by username_3 on 2011-02-12. Score: 23 | Accepted answer

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/>


---

### Answer by username_2 on 2011-02-12. Score: 14

Assuming [standard conjecture](http://en.wikipedia.org/wiki/Cram%C3%A9r%27s_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.

> **Comments:**
> **username_3**: I'm curious as to how standard Cramér's conjecture is. I was under the impression that the odds were against it.  
> **username_2**: @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'.  
> **username_3**: @ 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  
> **username_2**: @Cong: Seems like a nice reading, I'll go through it in a few days!  

---

