Re: [obm-l] Complexidades P e NP

[Rodrigo Malta Schmidt <rodrigo.schmidt@xxxxxxxxxxxxx>]

Ola,

Uma pequena correcao nas colocacoes do Vinicius...

> 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 classe P eh a classe dos problemas que podem ser RESOLVIDOS por
algoritmos deterministicos em tempo polinomial (e nao a classe dos
problemas que tem sua resposta verificada em tempo polinomial).

De forma semelhante, a classe NP eh a classe dos problemas que podem ser
RESOLVIDOS por algoritmos nao-deterministicos em tempo polinomial no
tamanho da entrada. Isto eh equivalente a dizer que uma resposta pode
ser VERIFICADA deterministicamente em tempo polinomial.

Abracos,
Rodrigo
=========================================================================
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>
=========================================================================