Re: [obm-l] P e NP

[Carlos Maçaranduba <soh_lamento@xxxxxxxxxxxx>]

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

 

--- "Domingos Jr." <dopikas@uol.com.br> escreveu: >
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>
>
========================================================================= 

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