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

[Vinicius José Fortuna <vinicius.fortuna@xxxxxxxxxxxxx>]

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" <rodrigo.schmidt@ic.unicamp.br>
To: <obm-l@mat.puc-rio.br>
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 é <nicolau@mat.puc-rio.br>
=========================================================================