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 � <[EMAIL PROTECTED]> =========================================================================
