--- Carlos Ma�aranduba <[EMAIL PROTECTED]> escreveu: > 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. > > > Bom, coincidentemente estou estudando Grafos e Teoria da Complexidade na faculdade...� o seguinte: P � o conjunto dos problemas polinomiais, que s�o resolvidos, para um n�mero grande de elementos, em tempo aceit�vel; NP � o conjunto de problemas exponenciais, que, para grandes n�meros de elemento, n�o podem ser resolvidos em tempo aceit�vel por computadores atuais - por�m, a VERIFICA��O de uma resposta pode ser feita em tempo polinomial (n�o � poss�vel achar uma resposta em tempo polinomial, mas, com uma resposta em m�os, verificar se ela � verdadeira ou n�o requer um algoritmo apenas polinomial). NP-Completos s�o problemas NP para os quais n�o existem algoritmos polinomiais mas tamb�m n�o h� prova de que necessitem de algoritmos exponenciais - ou seja, eles s�o problemas NP sem solu��o atual por�m sem prova de que n�o s�o solucion�veis em tempo polinomial. Uma caracter�stica interessante � que todos os problemas da classe NP-Completo podem ser reduzidos a algum outro da mesma classe e ao problema de Satisfabilidade de circuitos (que � polinomial) e, portanto, a descoberta da solu��o polinomial de um problema NP-Completo acarreta na solu��o de todos os outros da classe. Essa propriedade e as redu��es de alguns algoritmos da classe foram mostradar por Cook em um �nico artigo (data e primeiro nome do sujeito me fogem agora...)
_______________________________________________________________________ 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]> =========================================================================
