Repare que no paper est� escrito �((log n)^12), com "til" no O. Essa nota��o tem um significado diferente. Para ser mais preciso, o algoritmo dos indianos leva, no pior caso, tempo O((log n)^12* f(log log n)), onde f � um polin�mio.
Para maiores informa��es sobre o paper, pode-se acessar o site: http://www.utm.edu/research/primes/prove/prove4_3.html Nessa p�gina h� um FAQ sobre o paper, seguindo o link "Primes in P little faq", que leva ao endere�o: http://crypto.cs.mcgill.ca/%7Estiglic/PRIMES_P_FAQ.html O conte�do dessa p�gina aborda v�rios pontos interessantes, inclusive o que s�o as classes de problemas P , NP e algumas outras. Pra quem � curioso vale a pena dar uma olhada. At� mais Vinicius Fortuna. IC-Unicamp ----- Original Message ----- From: "Rodrigo Malta Schmidt" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Sunday, August 25, 2002 6:17 PM Subject: Re: [obm-l] RES: [obm-l] Numeros primos - solu��o > > > 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 � <[EMAIL PROTECTED]> =========================================================================
