Re: [obm-l] Complexidades P e NP

[Vinicius José Fortuna <vinicius.fortuna@xxxxxxxxxxxxx>]

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" <edilon.silva@poli.usp.br>
To: <obm-l@mat.puc-rio.br>
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 é <nicolau@mat.puc-rio.br>
=========================================================================