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