NP-completo

Origem: Wikipédia, a enciclopédia livre.

Na teoria da complexidade computacional, a classe de complexidade NP-completo é o subconjunto dos problemas de decisão em NP de tal modo que todo problema em NP se pode reduzir a um dos problemas NP-completo. Pode-se dizer que os problemas de NP-completo são os problemas mais difíceis de NP e muito provavelmente não formem parte da classe de complexidade P. A razão é que se conseguisse encontrar uma maneira de resolver qualquer problema NP-completo rapidamente (em tempo polinomial) , então poderia ser utilizado algoritmos para resolver todos problemas NP rapidamente. Como exemplo de um problema NP-completo está o problema da soma dos subconjuntos que pode ser enunciado conforme segue: dado um conjunto S de inteiros, determine se há algum conjunto não vazio de S cujos elementos somem zero. É fácil de verificar se uma resposta é correta, mas não se conhece uma solução significativamente mais rápida para resolver este problema do que testar todos os subconjuntos possíveis, até encontrar um que cumpra com a condição.

Índice 1 Soluções Aproximadas 2 Exemplos 3 Ver também 4 Referências

[editar] Soluções Aproximadas

Atualmente todos os algoritmos conhecidos para problemas NP-completos utilizam tempo exponencial quanto ao tamanho da entrada. Se desconhece se há melhores algoritmos, pela qual, para se resolver um problema NP-completo de tamanho arbitrário se utiliza de um dos seguintes enfoques:

• Aproximação: Um algoritmo que rapidamente encontra uma solução não necessariamente ótima, contudo dentro de um certo intervalo de erro. Em alguns casos, encontrar uma boa aproximação é o suficiente para resolver o problema, porém nem todos os problemas NP-completos tem bons algoritmos de aproximação.
• Probabilístico: Um algoritmo que pode obter em média uma boa solução para um problema apresentado de uma distribuição de dados de entrada.
• Casos Particulares: Quando se reconhecem casos particulares do problema para os quais existem soluções rápidas..
• Heurísticas: Um algoritmo que trabalha razoavelmente bem em muitos casos, mas não há prova de que são sempre rápidos e que produzam sempre bons resultados.
• Algoritmo genético : Algoritmos que melhoram as possíveis soluções até encontram alguma que esteja próxima do ótimo. Contudo, também não existem formas de se garantir a qualidade da resposta.

[editar] Exemplos

Um problema interessante na Teoria dos grafos é o problema do isomorfismo dos grafos: Dois grafos são isomorfos se um pode se transformar em outro simplesmente renomeando-se os vértices. Considere se os dois problemas seguintes:

• Isomorfismo de Grafos: O grafos G₁ é isomorfo ao grafo G₂?
• Isomorfismo de Subgrafos: O grafos G₁ é isomorfo ao subgrafo do grafo G₂?

O problema de isomorfismo de subgrafos é NP-completo. O problema do isomorfismo do grafo é suspeito de não estar em P nem NP-completo, ainda que obviamente está em NP. Este é um exemplo de um problema que se imagina difícil, mas não tanto para estar em NP-completo. A forma mais fácil de demonstrar que um novo problema é NP-completo é primeiro demonstrar que ele está em NP, e então reduzi-lo para algum problema NP-completo já conhecido. Portanto, é muito útil conhecer-se uma variedade de problemas de já existe comprovação de que pertencem a NP-completo. A lista abaixo contém alguns dos problemas bem conhecidos como NP-completo quando expressados como problemas decisórios:

• Problema de satisfatibilidade booleana (SAT)
• Jogo do 15
• Problema da mochila (Knapsack)
• Tetris
• Problema do ciclo hamiltoniano
• Problema do Caixeiro-viajante
• Problema da Torre de Hanoi
• Problema de isomorfismo de subgráficos
• Problema da soma de subconjuntos
• Problema da clique
• Problema de cobertura de vértices
• Problema de conjuntos independentes

[editar] Ver também

• P versus NP

[editar] Referências

• Garey, M. and D. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, 1979. ISBN 0716710455 (Este é um livro clássico que desenvolve a teoria e classifica muitos dos problemas NP-completo).
• Complexidade Computacional de Jogos e Quebra-Cabeças – Em inglês.
• Tetris é difícil, mesmo que para aproximar-se – Em inglês.
• Campo Minado é NP-completo! – Em inglês.