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]> =========================================================================