Aspectos da Computação

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 NP-Completo e as
Classes P e NP
• Classe P
– Consiste nos problemas que podem ser resolvidos em tempo polinomial

• Classe NP
– Consiste nos problema que são verificáveis em tempo polinomial
– Se tivéssemos de algum modo um “certificado” de uma solução, poderíamos verificar se o certificado é correto em tempo polinomial no tamanho da entrada para o problema

Caráter NP-Completo e as
Classes P e NP
• Classe NP
– Por exemplo, no problema do ciclo hamiltoniano, dado um grafo orientado G = (V, A), um certificado seria uma seqüência v1, v2, ..., v|V| de |V| vértices
– É fácil verificar em tempo polinomial que
• (vi, vi+1) ∈ A para i = 1, 2, ..., |V| - 1
• (v|V|, v1) ∈ A

• Qualquer problema em P também está em NP
– Se um problema está em P então podemos resolvê-lo em tempo polinomial sem sequer receber um certificado Caráter NP-Completo e as
Classes P e NP
• Classe NP-Completo
– Informalmente, um problema está na classe NPcompleto se ele está em NP e é tão “difícil” quanto qualquer problema em NP
– Se qualquer problema NP-completo pode ser resolvido em tempo polinomial, então todo problema
NP-completo tem algoritmo de tempo polinomial

Problemas de Decisão Versus
Problemas de Otimização
• Em problemas de otimização, cada solução possível tem um valor associado, e desejamos encontrar a solução possível com o melhor valor
– Por exemplo, no problema SHORTEST-PATH, temos um grafo não orientado G e vértices u e v, e
desejamos