Deixa eu ver se entendi bem.Os problemas P s�o resolvidos em tempo aceitavel(porque � da ordem de um polinomio)e fornece a resposta procurada com exatidao , por isso s�o deterministicos.Os NP s�o de ordem exponencial e os computadores atuais levariam muito tempo para achar a resposta e o que se faz � o uso de t�cnicas probabilisticas(portanto nao deterministicas) em tempo polinomial para se achar a resposta.Um problema x NP completo ,� o representante de uma classe de problemas que p�dem ser reduzidos a x e portanto seriam NP. Agora uma coisa que nao ficou clara � por que se define NP como uma verifica��o de resposta e n�o como uma busca de resposta.� porque como a solu��o � probabilistica , dado que eu a achei, devo verificar a resposta???Se assim for,toda verifica��o de resposta � em tempo polinomial???Como seria??
--- "Domingos Jr." <[EMAIL PROTECTED]> escreveu: > 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]> > ========================================================================= _______________________________________________________________________ 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]> =========================================================================
