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