Re: [obm-l] P e NP

["Domingos Jr." <dopikas@xxxxxxxxxx>]

Basicamente problemas da classe P são aqueles para os quais existe um
algoritmo que determina a(s) solução(ões) em tempo polinomial, problemas NP
são aqueles problemas considerados difíceis pois não existe solução
polinomial, só exponencial.

Não-determinístico quer dizer que envolve algo aleatório, o que você leu
provavelmente não tem muito a ver com a definição de NP, mas talvez com
algum comentário a respeito de um problema específico.

Até pouco tempo atrás o problema de verificar se um número é primo (PRIMES)
só era possível em tempo polinomial usando algoritmos não determinísticos
(são algoritmos que dizem que o número é primo com um certo grau de
confiança, mas não uma certeza absoluta). O algoritmo dos indianos, o AKS
definitivamente colocou PRIMES em P, pois é um algoritmo determinístico (te
dá absoluta certeza se o número é ou não primo) em tempo polinomial.

Para exemplos de problemas NP-completo temos o caso do caxeiro viajante
(muito famoso), problemas de grafos, otimização inteira etc... uma pequena
busca na internet vai te retornar muitos links para esses assuntos.

esse aqui parece ser interessante:
http://www.dcc.ufmg.br/~wesley/aeds3/relatorio.html

----- Original Message -----
From: "Carlos Maçaranduba" <soh_lamento@yahoo.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Saturday, November 09, 2002 8:26 PM
Subject: [obm-l] P e NP


> Já vi várias definiçoes sobre problemas P e NP e não
> consegui entender direito.Afinal estas estimativas
> estão relacionadas a o tempo de ACHAR UMA RESPOSTA QUE
> SATISFAÇA O PROBLEMA ou COM UMA SUPOSTA RESPOSTA EM
> MÂOS,VERIFICAR SE ELA É VÁLIDA????O que seria entao
> problemas NP-COMPLETOS???Qual o sentido do
> "não-deterministico" do NP???? O que significa
> P=NP????
> Enfim quem puder esclarecer junto com exemplos ficarei
> grato.
>
>
> _______________________________________________________________________
> Yahoo! GeoCities
> Tudo para criar o seu site: ferramentas fáceis de usar, espaço de sobra e
acessórios.
> http://br.geocities.yahoo.com/
> =========================================================================
> 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>
> =========================================================================

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