Basicamente problemas da classe P s�o aqueles para os quais existe um algoritmo que determina a(s) solu��o(�es) em tempo polinomial, problemas NP s�o aqueles problemas considerados dif�ceis pois n�o existe solu��o polinomial, s� exponencial.
N�o-determin�stico quer dizer que envolve algo aleat�rio, o que voc� leu provavelmente n�o tem muito a ver com a defini��o de NP, mas talvez com algum coment�rio a respeito de um problema espec�fico. At� pouco tempo atr�s o problema de verificar se um n�mero � primo (PRIMES) s� era poss�vel em tempo polinomial usando algoritmos n�o determin�sticos (s�o algoritmos que dizem que o n�mero � primo com um certo grau de confian�a, mas n�o uma certeza absoluta). O algoritmo dos indianos, o AKS definitivamente colocou PRIMES em P, pois � um algoritmo determin�stico (te d� absoluta certeza se o n�mero � ou n�o primo) em tempo polinomial. Para exemplos de problemas NP-completo temos o caso do caxeiro viajante (muito famoso), problemas de grafos, otimiza��o inteira etc... uma pequena busca na internet vai te retornar muitos links para esses assuntos. esse aqui parece ser interessante: http://www.dcc.ufmg.br/~wesley/aeds3/relatorio.html ----- Original Message ----- From: "Carlos Ma�aranduba" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Saturday, November 09, 2002 8:26 PM Subject: [obm-l] P e NP > J� vi v�rias defini�oes sobre problemas P e NP e n�o > consegui entender direito.Afinal estas estimativas > est�o relacionadas a o tempo de ACHAR UMA RESPOSTA QUE > SATISFA�A O PROBLEMA ou COM UMA SUPOSTA RESPOSTA EM > M�OS,VERIFICAR SE ELA � V�LIDA????O que seria entao > problemas NP-COMPLETOS???Qual o sentido do > "n�o-deterministico" do NP???? O que significa > P=NP???? > Enfim quem puder esclarecer junto com exemplos ficarei > grato. > > > _______________________________________________________________________ > Yahoo! GeoCities > Tudo para criar o seu site: ferramentas f�ceis de usar, espa�o de sobra e acess�rios. > http://br.geocities.yahoo.com/ > ========================================================================= > 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]> > ========================================================================= ========================================================================= 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]> =========================================================================
