NP-completo

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.

Soluções Aproximadas

Atualmente todos os algoritmos conhecidos para problemas NP-completos utilizam tempo exponencial com 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.

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 subgráficos é 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:

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.

Algoritmos

Gourt Home::Gourt :: NP-completo

Soluções Aproximadas

Exemplos

Referências