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]>
=========================================================================
