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.) 
Finding a prime greater than a given bound
cc.complexity theory;open problem;nt.number theory;polynomial time;primes
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_primesCurrently 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/