On Sun, Nov 10, 2002 at 01:35:24PM -0300, Domingos Jr. wrote: > 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 � bem assim. NP n�o significa n�o-polinomial, significa "nondeterministic polynomial". Ou seja, se voc� tiver sorte (ou uma ilumina��o sobrenatural), o problema NP passa a ser polinomial. Uma outra forma de dizer isso � que voc� deve poder *verificar* uma solu��o (talvez surpreendente) que algu�m te mostre em tempo polinomial. Os problemas verdadeiramente dif�ceis s�o exponenciais mesmo e se voc� tiver sorte de "adivinhar" a resposta ainda � exponencialmente dif�cil verificar a resposta. > > 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. O exemplo do caixeiro viajante � bom: determinar se existe um caminho ou circuito hamiltoniano em um grafo � (ou pelo menos parece ser) um problema dif�cil. Por outro lado, se algu�m te mostrar um caminho hamiltoniano � bem f�cil verificar que o caminho �, de fato, hamiltoniano... Um exemplo de problema NP � verificar que um grafo pode ser pintado com tr�s cores sem que v�rtices da mesma cor fiquem sendo vizinhos: se voc� adivinhar a resposta � f�cil verificar que ela est� certa. Um exemplo de problema realmente dif�cil (n�o NP) � verificar que um grafo *n�o* pode ser pintado com tr�s cores: mesmo que um mago poderos�ssimo soubesse que o grafo n�o pode ser pintado e desejasse convercer voc� deste fato ele e voc� teriam uma tarefa dif�cil pela frente. []s, N. ========================================================================= 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]> =========================================================================
