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