Re: [obm-l] P e NP

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

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 � <nicolau@mat.puc-rio.br>
=========================================================================