Re: [obm-l] P e NP

[Tays Soares <tayscristina@xxxxxxxxxxxx>]

 --- Carlos Maçaranduba <soh_lamento@yahoo.com.br>
escreveu: > 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.
> > >
Bom, coincidentemente estou estudando Grafos e Teoria
da Complexidade na faculdade...é o seguinte:
P é o conjunto dos problemas polinomiais, que são
resolvidos, para um número grande de elementos, em
tempo aceitável; NP é o conjunto de problemas
exponenciais, que, para grandes números de elemento,
não podem ser resolvidos em tempo aceitável por
computadores atuais - porém, a VERIFICAÇÂO de uma
resposta pode ser feita em tempo polinomial (não é
possível achar uma resposta em tempo polinomial, mas,
com uma resposta em mãos, verificar se ela é
verdadeira ou não requer um algoritmo apenas
polinomial). NP-Completos são problemas NP para os
quais não existem algoritmos polinomiais mas também
não há prova de que necessitem de algoritmos
exponenciais - ou seja, eles são problemas NP sem
solução atual porém sem prova de que não são
solucionáveis em tempo polinomial. Uma característica
interessante é que todos os problemas da classe
NP-Completo podem ser reduzidos a algum outro da mesma
classe e ao problema de Satisfabilidade de circuitos
(que é polinomial) e, portanto, a descoberta da
solução polinomial de um problema NP-Completo acarreta
na solução de todos os outros da classe. Essa
propriedade e as reduções de alguns algoritmos da
classe foram mostradar por Cook em um único artigo
(data e primeiro nome do sujeito me fogem agora...)

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