Re: [obm-l] P e NP

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

On Mon, Nov 11, 2002 at 04:28:01PM -0200, Nicolau C. Saldanha wrote:
> 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.

Falando em computadores atuais, computadores quânticos mudariam
muito o nosso poder de resolver problemas. Existe toda uma classe
QP de problemas que são quanticamente polinomiais, i.e., demoram
tempo polinomial em um computador quantico. Conjectura-se que
P esteja estritamente contido em QP que por sua vez estaria
estritamente contido em NP. Um exemplo de problema em QP mas
provavelmente não em P é o de fatorar inteiros. Por outro lado
ninguém sabe provar sequer que P e NP são diferentes então é
possível (mas improvável) que estas três classes afinal de contas
sejam iguais.

Há uma matéria boa sobre computação quântica na última Scientific American.
Vale a pena.

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