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.)
$\begingroup$
$\endgroup$
2
-
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$– KavehCommented Feb 12, 2011 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 張顯之Commented Feb 12, 2011 at 19:50
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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/
$\begingroup$
$\endgroup$
4
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.
answered Feb 12, 2011 at 19:46
-
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 HanCommented Feb 13, 2011 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$ Commented Feb 14, 2011 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 HanCommented Feb 14, 2011 at 5:23
-
$\begingroup$ @Cong: Seems like a nice reading, I'll go through it in a few days! $\endgroup$ Commented Feb 14, 2011 at 5:50