Possible Duplicate:Finding a prime greater than a given bound QuestionDoes there exista 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.)ContextSuppose 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.KnownWe have deterministic construction of irreducible polynomials: http://www.sciencedirect.com/science/article/pii/S074771718471025XWe also have deterministic primality checking: http://en.wikipedia.org/wiki/AKS_primality_testBy 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)$.
Deterministic Prime Construction
cc.complexity theory