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