Finding a prime greater than a given bound Is a deterministic polynomial-time algorithm known for the following problem: 

Input: a natural number $n$ (in binary encoding)

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

(According to a list of open problems by Leonard Adleman, the problem was open in 1995.)
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. 

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&gt;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/