Encontrando um primo maior que um determinado limite

25

É 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.)

Vincenzo
fonte
1
+1: Lembrou-me que o problema de decisão natural correspondente não é o teste de primalidade (que está em ), mas o seguinte problema: dado a < b , existe um número primo no intervalo [ a , b ] ? Pa<b[a,b]
Kaveh
@ Kaveh: Três dedos apontando para mim, eu acho. Deveríamos estabelecer uma política que proíbe respostas nos comentários;)
Hsien-Chih Chang 12 之

Respostas:

23

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>NO(N1/2+o(1))

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

Atualmente, o projeto procura responder à seguinte pergunta:

NN2NO(N1/2c)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/

Cong Han
fonte
14

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

pnpn+1pn=O(log2pn)

nn+1nn

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

Hsien-Chih Chang 張顯 之
fonte
1
Estou curioso para saber como a conjectura de Cramér é padrão. Fiquei com a impressão de que as chances eram contrárias.
Cong Han
@ Cong: Eu não estou realmente familiarizado com a conjectura, e minha impressão é que temos evidências em resultados numéricos e isso também se aplica ao modelo aleatório. Há alguma indicação de que a conjectura possa ser falsa? Talvez eu deva declarar 'forte' em vez de 'padrão'.
Hsien-Chih Chang # 14/02/11
@ Hsien-Chih: Eu sei muito pouco sobre isso (além de alguns boatos e interesse nos projetos Polymath), mas este artigo de Granville, vinculado a partir do wiki sobre a conjectura, parece sugerir isso: dartmouth.edu/~ chance / chance_news / for_chance_news / Riemann /…
Cong Han
@ Can: Parece uma boa leitura, vou passar por isso em alguns dias!
Hsien-Chih Chang # 14/02/11