[obm-l] RES: [obm-l] Numeros primos - solu��o

["Edilon Ribeiro da Silva" <edilon.silva@xxxxxxxxxxx>]

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: DEOLIVEIRASOU@aol.com [mailto:DEOLIVEIRASOU@aol.com] 
	Enviada: dom 25/8/2002 15:15 
	Para: obm-l@mat.puc-rio.br 
	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