Encontrando um primo maior que um determinado limite

É um algoritmo de tempo polinomial determinístico conhecido pelo seguinte problema:

Entrada: um número natural (em codificação binária)$n$

Saída: um número primo .$p > n$

(De acordo com uma lista de problemas em aberto de Leonard Adleman, o problema foi aberto em 1995.)

O melhor resultado foi incondicional corrente dada por Odlyzko, que encontra um primo em S ( N 1 / 2 + S ( 1 ) ) tempo. A forte conjectura no projeto Polymath4 procura resolver se isso pode ser feito em tempo polinomial, sob suposições razoáveis ​​da teoria dos números, como o GRH.$p >N$$O(N^{1/2 + o(1)})$

http://michaelnielsen.org/polymath1/index.php?title=Finding_primes

Atualmente, o projeto procura responder à seguinte pergunta:

$N$$N$$2N$$O(N^{1/2 - c})$$c>0$

Até agora, eles têm uma estratégia que determina a paridade do número de primos no intervalo.

http://polymathprojects.org/2010/06/29/draft-version-of-polymath4-paper/

Assumindo a conjectura padrão na teoria dos números, que afirma que

$p_n$$p_{n+1}-p_n = O(\log^2 p_n)$

$n$$n+1$$n$$n$

Mas não tenho certeza se isso pode ser provado incondicionalmente.