Re: [[obm-l] Quem sabe?]

["David Ricardo" <davidrvp@xxxxxxxxxxxx>]

Na verdade, o conjunto NP é o conjunto dos problemas Não-determinísticos
Polinomiais, ou seja, são problemas em que os algoritmos que tentam
resolvê-los "chutam uma resposta" e verificam se a resposta é valida em
tempo polinomial.

Os problemas do tipo P são aqueles em que é possível se desenvolver um
algoritmo com complexidade polinomial para se obter uma resposta.

Ninguém nunca conseguiu provar se P = NP, ou seja, se todos os problemas NP
podem ser resolvidos por um algoritmo em P. Há pessoas que acham que sim,
mas isso nunca foi provado.

[]s
David

----- Original Message -----
From: "Artur Costa Steiner" <artur_steiner@usa.net>
To: <obm-l@mat.puc-rio.br>
Sent: Tuesday, June 03, 2003 11:50 AM
Subject: Re: [[obm-l] Quem sabe?]


> "André W.Hirano" <awhirano@pqi-usp.zzn.com> wrote:
> > P=NP
> Eu jah vi estas siglas serem usada para algritmos. P signfica polinomial e
NP
> nao-polinomial. Polinomial significa que o numero esperdo de iteracoes
> necessarias para a convergencia depende polinomialmente ds soma do numero
de
> variaveis com o de retricoes. Eu jah vi P = NP, mas no momento nao me
lenbro
> do que eh.
> Artur

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