Possible Duplicate:
Finding a prime greater than a given bound
Question
Does there exist
- a polynomial $q$
and a deterministic polynomial time algorithm $A$
such that for all sufficiently large $n$, we have:
$A(n)$ outputs a prime $p$ s.t. $n \leq p \leq q(n)$. (Note $n$ is stored in binary, so $A$ must run in $poly(\log n)$ time.)
Context
Suppose that for some derandomization task we need to be able to construct primes. This rules out the "guess a random number + check" approach since we can't use randomness.
Known
We have deterministic construction of irreducible polynomials: http://www.sciencedirect.com/science/article/pii/S074771718471025X
We also have deterministic primality checking: http://en.wikipedia.org/wiki/AKS_primality_test
By http://en.wikipedia.org/wiki/Bertrand_postulate there is a prime between $n$ and $2n-2$, but we can't check all $n$ numbers in $poly(\log n)$ time.
By http://en.wikipedia.org/wiki/Prime_number_theorem we know that $\pi(x) \sim \frac{x}{\ln x}$, but it's not clear that this implies there is a prime between $n$ and $n+O(\log n)$.
