Re: [obm-l] RES: [obm-l] Numeros primos - solução

[Rodrigo Malta Schmidt <rodrigo.schmidt@xxxxxxxxxxxxx>]

Ola,

> 
> A classe de todas as linguagens polinomialmente decidíveis é denotada por P [P do inglês polinomial] e 
> a classe de todas as linguagens que não pertecem a P é denotada por NP [NP do inglês no-polinomial]. 

NP vem do ingles "nondeterministic polynomial time". Problemas (ou
linguagens, como voce definiu) em NP nao sao necessariamente
nao-polinomiais. Se fossem, teriamos resposta para o problema P=NP. NP
representa a classe de problemas para os quais se consegue um algoritmo
nao-deterministico que rode em tempo polinomial (equivalente a se
conseguir verificar uma saida deterministicamente em tempo polinomial).
Todo problema em P necessariamente esta em NP, mas o inverso ainda eh um
problema em aberto.

> 
>     De acordo com o documento "Primes in P", os autores apresentam um algoritmo que decide se um dado 
> número n é primo ou composto [dei uma lida rápida] com uma complexidade computacional O([log(n)]^6), 
> podendo futuramente chegar a O([log(n)]^3), desde que se prove a conjectura de Bhattacharjee-Pandey.

Talvez minha olhada tenha sido mais rapida que a sua, mas eu havia lido
o seguinte:

"We give  a deterministic, O((log n)^12) time algorithm for testing if a
number is prime. Heuristically, our algorithm does much better: under a
widely believed conjecture on the density of Sophie Germain primes
(primes p such that 2p+1 is also prime), the algorithm takes only O((log
n)^6) steps."

Mas realmente, no final do artigo, seguindo outras conjecturas os
autores comentam a possibilidade de uma implementacao O((log n)^3). No
entanto, enquanto a Conjectura 5 do artigo (Sophie Germain) ainda nao
for provada, o algoritmo deles continua tendo complexidade
deterministica O((log n)^12), o que, para numeros com 1000 bits por
exemplo, nao eh muito viavel na pratica.

Minhas referencias sao dos livros:

  Introduction to Algorithms. Thomas Cormen et al.
  Introduction to Algorithms - A creative approach. Udi Manber.

e do artigo:

  PRIMES is in P. Agrawal, Kayal e Saxena.

Abracos,
Rodrigo
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================