A seguinte proposi��o � verdadeira: Todo problema pertencente � classe de complexidade P pertence � classe de complexidade NP.
A classe "P" significa que a solu��o pode ser verificada em tempo polinomial. A classe NP significa que a solu��o pode ser verificada n�o-deterministicamente em tempo polinomial. A proposi��o de que P est� contido em NP vem justamente do fato de que tudo que � determin�stico pode ser considerado como n�o-determin�stico. A rec�proca da proposi��o � um problema em aberto. Existe um subconjunto dos NP que s�o os NP-completos. Todo problema NP se reduz polinomialmente a um problema NP-completo. Isso quer dizer que sempre � poss�vel transformar um problema NP em tempo polinomial em um caso particular de um NP-completo. Dessa forma, se um problema NP-completo puder ser resolvido em tempo polinomial, ent�o, todos os NP tamb�m poder�o e ent�o teremos P=NP. Acredita-se que P � diferente de NP. Eu preferiria que fossem iguais, as coisas seriam bem mais f�ceis. :-) Maiores informa��o pode-se encontrar em qualquer livro de complexidade de algoritmos At� mais Vinicius Fortuna Ci�ncia da Computa��o - Unicamp ----- Original Message ----- From: "Edilon Ribeiro da Silva" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Wednesday, August 14, 2002 8:34 PM Subject: [obm-l] Complexidades P e NP > Gostaria de saber se existe algum problema que perten�a simultaneamente � classe de complexidade P e � classe de compleidade NP. > > Edilon Ribeiro. ========================================================================= 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]> =========================================================================
