Re: [obm-l] P e NP

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

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 é <nicolau@mat.puc-rio.br>
=========================================================================