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, com uma redução de tempo polinomial, 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 |
[editar] Soluções Aproximadas
Atualmente todos os algoritmos conhecidos para problemas NP-completos utilizam tempo exponencial quanto ao tamanho da entrada. Desconhece-se a existência de melhores algoritmos 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 G1 é isomorfo ao grafo G2?
- Isomorfismo de Subgrafos: O grafos G1 é isomorfo ao subgrafo do grafo G2?
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 uma variedade de problemas que já têm comprovação de serem NP-completos. 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 de Roteamento de Veículos
- 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
[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.
