On Sun, Nov 10, 2002 at 05:51:19PM -0300, Carlos Ma�aranduba wrote: > Deixa eu ver se entendi bem.Os problemas P s�o > resolvidos em tempo aceitavel(porque � da ordem de um > polinomio)e fornece a resposta procurada com exatidao > , por isso s�o deterministicos.Os NP s�o de ordem > exponencial e os computadores atuais levariam muito > tempo para achar a resposta e o que se faz � o uso de > t�cnicas probabilisticas(portanto nao deterministicas) > em tempo polinomial para se achar a resposta.Um > problema x NP completo ,� o representante de uma > classe de problemas que p�dem ser reduzidos a x e > portanto seriam NP. > Agora uma coisa que nao ficou clara � por que se > define NP como uma verifica��o de resposta e n�o como > uma busca de resposta.� porque como a solu��o � > probabilistica , dado que eu a achei, devo verificar a > resposta???Se assim for,toda verifica��o de resposta � > em tempo polinomial???Como seria??
Acabo de comentar em outro e-mail. Problemas NP s�o exatamente aqueles cuja resposta pode ser verificada em tempo polinomial. Nem todo problema dif�cil � assim, claro. Estamos sempre falando de responder a pergunta com certeza, n�o de m�todos probabil�sticos. []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 � <[EMAIL PROTECTED]> =========================================================================
