Finding a prime greater than a given bound
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/