Caro Crom,
---------------------------------------------------------------------------
Existem problemas de decis�o bem definidos que n�o podem ser resolvidos por
algoritmos. Podemos, portanto, classificar todos os problemas computacionais em duas
categorias: aqueles que podem ser resolvidos por algoritmos e aqueles que n�o podem.
Com os grandes avan�os da tecnologia da computa��o das �ltimas d�cadas, � razo�vel
esperar que todos os problemas do primeiro tipo possam ser resolvidos de uma maneira
satisfat�ria. Infelizmente, a pr�tica da computa��o revela que muitos problemas,
apesar de sol�veis a princ�pio, n�o podem ser resolvidos em qualquer sentido pr�tico
por computadores devido �s excessiva exig�ncias de tempo.
Suponha, por exemplo, que sua tarefa � escalonar a visita de um caixeiro viajante
a 10 escrit�rios regionais. Voc� recebe um mapa com as 10 cidades e as dist�ncias em
kil�metros e lhe pedem para produzir um intiner�rio que minimiza a dist�ncia total
percorrida. Esse �, claramente, o tipo de tarefa em que voc� utilizaria um computador
para resolver. E, de um ponto de vista te�rico, o problema � certamente sol�vel. Se h�
n cidades para visitar, o n�mero de itiner�rios poss�veis � finito - para ser presciso
(n-1)!. Portanto, pode-se facilmente conceder um algoritmo que sistematicamente
examina todos os intiner�rios a fim de localizar o mais curto.
Mas ainda h� um mal-estar com rela��o a esse algoritmo. H� muitas viagens a serem
examinadas. Para nosso modesto problema de 10 cidades, ter�amos de examinar 9! =
362.880 itinar�rios. Com alguma paci�ncia, isso pode ser realizado por um computador,
mas e se tiv�ssemos 40 cidades a visitar? O n�mero de itiner�rios seria agora
gigantesco: 39!, o que � mais que 10^45. Mesmo que pud�ssemos examinar 10^15 viagens
por segundo - um passo que � muito r�pido mesmo para o mais poderoso supercomputador
existente ou projetado - o tempo exigido para completar esse c�lculo seria v�rios
bilh�es de ciclo de vida do universo!
Evidentemente, o fato de um problema ser sol�vel na teoria n�o imediatamente
implica que ele possa ser resolvido de maneira realista na pr�tica. A quest�o �: quais
algoritmos devemos considerar como praticamente vi�vel?
Como o exemplo do PROBLEMA DO CAIXEIRO VIAJANTE revela, o par�metro limitador � o
tempo ou n�mero de passos exigidos pelo algoritmo em um entrada. O algoritmo (n-1)!
para o problema do caixeiro viajante foi demasiado irreal simplemente por causa do
excessivo crescimento exponencial de suas exig�ncias de tempo (� f�cil ver que a
fun��o (n-1)! cresce ainda mais r�pido que 2^n). Em contraste, um algoritmo com uma
taxa de crescimento polinomial seria obviamente muito mais atraente.
Parece que, a fim de capturar a no��o de "algotitmo praticamente vi�vel", devemos
limitar nossos dispositivos computacionais para somente executar um n�mero de passo
que � limitado por um polin�mio no comprimento de entrada [da� a import�ncia da
descoberta dos cientistas da Computa��o indianos]. 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]. Isso justifica o t�tulo do artigo dos cientistas: PRIMES IN P.
Em que medida a classe P captura a no��o intuitiva de "problema satisfatoriamente
vi�vel"? Com que amplitude se aceita a tese de que algoritmos polinomiais s�o
precisamente ou empiricamente vi�veis? � razo�vel dizer que, embora seja a �nica
proposta s�ria nessa �rea, ela pode ser desafiada em v�rios terrenos. Por exemplo,
pode-se argumentar que um algoritmo com exig�ncias de tempo n^100 ou mesmo
(10^100)n^2, n�o � "praticamente vi�vel", embora tenha um tempo polinomial. Al�m
disso, um algoritmo com exig�ncias de tempo n^(log(log(n)) pode ser considerado
perfeitamente vi�vel na pr�tica, a despeito do fato de que seu crescimento n�o �
limitado por qualquer polin�mio. O argumento emp�rico em defesa de nossa tese � que
tais limites extremos de tempo, embora teoricamente poss�veis, raramente ocorrem na
pr�tica: algoritmos polinomiais, que surgem em pr�ticas computacionais, geralmente t�m
pequenos expoentes e coeficientes costantes agrad�veis, enquanto algoritmos n�o
polinomiais s�o em geral exponenciais e, portanto, de utliza��o bastante limitada na
pr�tica.
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.
---------------------------------------------------------------------------
Notas:
1) Este texto acima foi, essencialmente, retirado do cap�tulo 6, se��es 6.1 e
6.2, do livro ELEMENTOS DE TEORIA DA COMPUTA��O [Trad. Edson Furmankiewicz] de Harry
R. Lewis e Christos H. Papadimitriou, 2� Edi��o, Bookman, Porto Alegre, 2000.
2) Os acr�scimos e as supress�es por mim feitas objetivaram apenas tornar a
leitura mais adequada aos prop�sitos da mensagem.
3) Citem sempre a refer�ncia, qualquer que seja o texto. Respeitem os direitos
autorais.
---------------------------------------------------------------------------
Obrigado,
Edilon Ribeiro
-----Mensagem original-----
De: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]]
Enviada: dom 25/8/2002 15:15
Para: [EMAIL PROTECTED]
Cc:
Assunto: Re: [obm-l] Numeros primos - solu��o
O que significa: " Em tempo polinomial ", como foi citado no texto sobre a
f�rmula dos matem�ticos hindus, para numeros primos????
Um abra�o
Crom
winmail.dat
Description: application/ms-tnef
