P NP

1493 palavras 6 páginas

P, NP e NP-Completo
Andre´ Vignatti
DINF- UFPR

´
Problemas Dif´ıceis, Problemas Faceis
O mundo esta´ cheio de problemas de busca.
Alguns podem ser resolvidos eficientemente, outros parecem ser muito dif´ıceis.
Isto e´ descrito na tabela a seguir:
Problemas dif´ıceis
3SAT
CAIXEIRO VIAJANTE
LONGEST PATH
3D MATCHING
MOCHILA
INDEPENDENT SET
ZERO-ONE EQUATIONS
RUDRATA PATH
MAXIMUM CUT

´
Problemas faceis
2SAT, HORN SAT
´
ARVORE
GERADORA M´INIMA
SHORTEST PATH
BIPARTITE MATCHING
´
MOCHILA fracionaria
´
INDEPENDENT SET em arvores
´
ZOE fracionario
EULER PATH
MINIMUM CUT

A. Vignatti

P, NP e NP-Completo

´
Problemas Dif´ıceis, Problemas Faceis

˜ resolvidos eficientemente.
Na direita temos problemas que sao
˜
A` esquerda, temos “nozes duras” que escaparam da soluc¸ao
´
´ eficiente durante decadas ou seculos.
˜ resolvidos por algoritmos
Os problemas a` direita sao
˜ dinamica,
ˆ
especializados e diversos: programac¸ao fluxo de rede, busca em grafo, gulosos.
˜ faceis
´
´
˜ diferentes.
Estes problemas sao por varias razoes A. Vignatti

P, NP e NP-Completo

´
Problemas Dif´ıceis, Problemas Faceis

˜ todos dif´ıceis
Em contraste, os problemas da esquerda sao
˜
pela mesma e unica
´
razao:
˜ todos o mesmo problema, apenas com
No fundo, eles sao diferentes disfarces!

Em outras palavras...
˜ equivalentes: cada um pode ser reduzido a
Todos sao qualquer outro e vice-versa.

A. Vignatti

P, NP e NP-Completo

NP (a.k.a Problemas de Busca)
E´ hora de introduzir alguns conceitos importantes.
Lembrando: um problema de busca e´ aquele onde uma
˜ proposta pode ser rapidamente verificado quanto a` soluc¸ao ˜ correc¸ao. Denotamos a classe de todos os problemas de busca como
NP.
˜ Classe NP
Definic¸ao:
A classe NP e´ a classe de TODOS os problemas de busca.

A. Vignatti

P, NP e NP-Completo

P
Muitos problemas NP (i.e, de busca) podem ser resolvidos em tempo polinomial.
ˆ
Nesses casos, existe algoritmo que recebe uma instancia
I e tem
˜ polinomial em func¸ao
˜ de |I|. tempo de execuc¸ao

Relacionados

P np np completo
368 palavras | 2 páginas

P NP E NP-Completo Para resolver problemas de busca podemos usar vários tipos de algoritmos para que possamos executar buscas cada vez mais rápidas e eficientes com menor tempo possível. Hoje temos vários tipos de problemas e em algoritmo podemos separa-los por tipos P (classe problemas polinomiais que podem ser resolvidos com determinado tempo), NP ( classe de todos problemas polinomial tempo não determinístico ), NP-Completo (classe problemas muito difíceis pois todos problemas são reduzidos….

exibir mais
Complexidade de Algoritmos - Problema P versus NP
2189 palavras | 9 páginas

o programa é considerado rápido. Se, entretanto, a dependência do tempo for exponencial o programa é considerado lento. 2. Classe P de problemas A classe P de problemas é o conjunto de todos os problemas polinomiais, ou seja, o conjunto de problemas que têm complexidade O( N k ) para algum k. Para muitos problemas não sabemos (ainda) se ele está ou não em P, pois ainda não descobrimos um algoritmo polinomial nem conseguimos demonstrar que um tal algoritmo não existe. Exemplos: Alguns Problemas….

exibir mais
Resumo de expectativas da educação étnico-racial
203807 palavras | 816 páginas

SI M E NP SI SI EM PE N SI EM PE N SI EM PE N SI NP SI EM PE N SI PE IN S EM PE N SI EM PE N SI EM PE N SI EM PE N SI PE IN S EM PE N SI M EM PE N SI EM PE N SI PUBLICAÇÕES INSTITUCIONAIS EM PE N SI EM PE N SI EM PE N SI EM M ACESSIBILIDADE ARQUITETÔNICA EM PE EE E M EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI E PE N SI EM PE N SI EE NP SI N SI EM PE N SI EM PE N SI EM P PE P IN E M N S….

exibir mais
Aspectos da Computação
1077 palavras | 5 páginas

Problemas NP-Completo Última alteração: 29 de junho de 2009 Problemas NP-Completo • Ainda não foi descoberto nenhum algoritmo de tempo polinomial para um problema NP-completo, nem ninguém ainda foi capaz de provar que não pode existir nenhum algoritmo de tempo polinomial para qualquer deles • Essa questão chamada P ≠ NP foi um dos mais profundos e surpreendentes problemas de pesquisa abertos na Ciência da Computação teórica desde que foi proposto pela primeira vez em 1971 Caráter….

exibir mais
Apostilapedagogica2011
285611 palavras | 1143 páginas

abril/2011 M EE SI S M EE P N SI EM M EE P N SI M EE P N SI M EE P N SI M EE P N SI NP SI M EE P N SI M EE P N SI M EE P N SI M EE P N SI SI M EE P N SI M EE P N SI N SI M EE P N SI M EE P N SI EE P N SI M EE P N SI M EE P N SI E PE N SI M EE P N SI M EE P N SI E NP I S N SI M EE P N SI M EE P N SI ÍNDICE M EE P N SI M EE P N SI E NP I S M M EE M EE E P P M M E N M N EE EE EM SI SI M EM NP EE P P E I E M E P P S N N E PE IN SI SI NP IN M PE I S N M S I S N E I S ........….

exibir mais
classes e subclasses NP
2143 palavras | 9 páginas

o significado da classe de algoritmos NP (não determinístico polinomial) assim como suas “subclasses”. Os problemas NP englobam soluções desde problemas computacionalmente simples até problemas conhecidos como difíceis ou intratáveis. A classe NP tem como “subclasses” os problemas: P (polinomiais), NP – Completo, Intermediário, NP – Difícil. O trabalho procura explorar soluções para estes tipos de problemas e é concluído com um exemplo de problema de classe NP, demostrando uma possível solução para….

exibir mais
Educação
156972 palavras | 628 páginas

....................... 123 EE NP SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI SI EM PE N SI EM PE N SI EM PE N SI EE NP SI EM PE N SI EM PE N SI EE NP SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI SIN LEGISLAÇÃO FEDERAL EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI EM PE N SI PE IN S EM PE N SI EM PE N SI S S P N EM SI IN EM PE S M N M PE obrigação….

exibir mais
ATC P2
625 palavras | 3 páginas

problema é dito de otimização. II. A teoria da complexidade restringe-se a problemas de decisão, já que o estudo de problemas NP-completos é aplicado somente para esse tipo de problema. III. Os problemas NP-Completos são considerados como os problemas mais difíceis em NP. Se qualquer problema NP-Completo pode ser resolvido em tempo polinomial, então todos os problemas em NP podem ser resolvidos da mesma forma. A análise permite concluir que A) apenas a afirmativa I está correta. B) apenas a afirmativa….

exibir mais
Projeto de Restauração Ambiental
1902 palavras | 8 páginas

controle da acidez do solo (aproximadamente 6 meses antes do plantio das mudas com amostra para análise de solo). Caso o solo necessite de correção será feito a Calagem (elevar o teor de cálcio trocável a 7 mmolc dm-3, e a quantidade da adubação de base (N-P-K), tendo como referência as recomendações propostas por RAIJ et al. (1997); 30 dias antes do plantio das mudas, á lanço e em área total, com auxílio de uma calcariadeira tratorizada). Adubação O adubo de base será colocado na sua respectiva quantidade….

exibir mais
Trabalho de Cartas de Controle
1470 palavras | 6 páginas

INSTITUTO DE ENSINO SUPERIOR E PESQUISA- INESP CARTA DE CONTROLE NP Ana Carolina do Amaral Ana Flávia Ribeiro Amaral Bruna Martiniano Ewaldo Soares Flavia Silva Mariana Lara Maynara Luiza Paula Karolina Farias Valquíria Castro Divinópolis, outubro de 2013 UNIVERSIDADE DO ESTADO DE MINAS GERAIS FUNDAÇÃO EDUCACIONAL DE DIVINÓPOLIS INSTITUTO DE ENSINO SUPERIOR E PESQUISA-INESP Engenharia de Produção – 6º Período CARTA DE CONTROLE NP Trabalho apresentado para obtenção de créditos relativos….

exibir mais

Outros Trabalhos Populares