NP-completo

Na teoria da complexidade computacional, a classe de complexidade é o subconjunto dos problemas 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 poderiam ser utilizados 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. Na prática, o conhecimento de NP-completo pode evitar que se desperdice tempo tentando encontrar um algoritmo de tempo polinomial para resolver um problema quando esse algoritmo não existe.

Resumo formal

NP-completo é um subconjunto de NP, o conjunto de todos os problemas de decisão cujas soluções podem ser verificadas em tempo polinomial; NP pode ser equivalentemente definida como o conjunto de problemas de decisão que podem ser solucionados em tempo polinomial em uma Máquina de Turing não determinística. Um problema p em NP também está em NPC Se e somente se todos os outros problemas em NP podem ser transformados em p em tempo polinomial.

Problemas NP-completo são estudados porque a habilidade de rapidamente verificar soluções para um problema (NP) parece correlacionar-se com a capacidade de resolver rapidamente esse problema (P). Não é sabido se todos os problemas em NP podem ser rapidamente resolvidos - isso é chamado de problema P versus NP. Mas se qualquer problema em NP-completo pode ser resolvido rapidamente, então todo problema em NP também pode ser, por causa da definição de NP-completo afirma que todo problema em NP deve ser rapidamente redutível para todo problema em NP-completo (ou seja, pode ser reduzido em tempo polinomial). Por causa disso, é geralmente falado que os problemas NP-completo são mais difíceis que os problemas NP em geral.

Definição formal de NP-completo

Um problema de decisão $\scriptstyle C$ é NP-completo se:

1. $\scriptstyle C$ está em NP, e
2. Todo problema em NP é redutível para $\scriptstyle C$ em tempo polinomial.

$\scriptstyle C$ pode ser mostrado que pertence à NP demostrando que uma solução candidata para $\scriptstyle C$ pode ser verificada em tempo polinomial.

Note que um problema que satisfaz a condição 2 é dito ser NP-difícil, se satisfizer a condição 1 ou não.

Uma consequência dessa definição é que se tivéssemos um algoritmo de tempo polinomial para $\scriptstyle C$, poderíamos resolver todos os problemas NP em tempo polinomial.

Background

O conceito de NP-completo foi introduzido em 1971 por Stephen Cook em um artigo chamado The complexity of theorem-proving procedures nas páginas 151-158 do Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, apesar do termo NP-completo não aparecer em nenhum lugar nesse artigo. Nessa conferência, houve um forte debate entre os cientistas sobre se os problemas NP-completo pudessem ser resolvidos em tempo polinomial em uma Máquina de Turing determinística. John Hopcroft levou todos ao consenso na conferência que a questão de se os problemas NP-completo são resolvíveis em tempo polinomial deveria ser adiada para ser resolvida em uma data posterior, pois ninguém tinha uma prova formal de suas afirmações de uma maneira ou de outra. Essa é conhecida como a questão se P = NP.

Ninguém ainda conseguiu determinar conclusivamente se os problemas NP-completo são de fato resolvíveis em tempo polinomial, fazendo desse um dos maiores problemas não solucionados da matemática. O Clay Mathematics Institute oferece 1 milhão de dólares de recompensa para quem fizer uma prova formal que P = NP ou que P ≠ NP.

No celebrado Teorema de Cook-Levin (independentemente provado por Leonid Levin), Cook provou que o Problema de satisfatibilidade booleana é NP-completo. Em 1972, Richard Karp provou que vários outros problemas também são NP-completo. Assim, existe uma classe de problemas NP-completo (além do problemas da satisfatibilidade booleana). Desde os resultados obtidos por Cook, milhares de outros problemas foram mostrados pertencer à NP-completo por reduções de outros problemas previamente mostrados como sendo NP-completo; muitos deles estão no livro de 1979 de Garey e Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness.

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 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 reduzir algum problema NP-completo já conhecido para ele. 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 do isomorfismo de subgrafos
• Problema da soma dos subconjuntos
• Problema do clique
• Problema de cobertura de vértices
• Problema de conjuntos independentes

Resolvendo problemas NP-completo

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.
• Restrição: Restringindo a estrutura da entrada, algoritmos mais rápidos são possíveis.
• Parametrização: Geralmente há algoritmos rápidos se certos parâmetros da entrada são fixos.
• 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.

Completude em diferentes tipos de redução

Na definição de NP-completo dada acima, o termo redução foi usado no significado de redução em tempo polinomial muitos para um.

Outro tipo de redução é a redução de Turing em tempo polinomial. Um problema $\scriptstyle X$ é Turing-redutível em tempo polinomial a um problema $\scriptstyle Y$ se, dada uma subrotina que solucione $\scriptstyle Y$ em tempo polinomial, pode-se escrever um programa que chama a subrotina e soluciona $\scriptstyle X$ em tempo polinomial. Isso contrasta com a redução muitos para um, que possui a restrição de que o programa só pode chamar a subrotina uma vez, e o valor de retorno da subrotina deve ser o valor de retorno do programa.

Se se define o análogo ao NP-completo com reduções de Turing ao invés de reduções muitos para um, o conjunto resultante de problemas não será menor que NP-completo; é uma questão em aberto se será maior.

Outro tipo de redução que é geralmente usada para definir NP-completude é a redução logaritmo-espacial muitos para um que é uma redução muitos para um que pode ser computada com apenas uma quantidade de espaço logarítmica. Uma vez que toda computação que pode ser feita em espaço logarítmico também pode ser feito em tempo polinomial, daí se existe uma redução logaritmo-espacial muitos para um então também existe uma redução em tempo polinomial muitos para um. Esse tipo de redução é mais refinada do que a usual redução em tempo polinomial muitos para um e nos permite distinguir mais classes como a P-completo. Se sob esses tipos de redução a definição de NP-completo muda ainda é um problema em aberto. Todos os problemas NP-completo conhecidos são NP-completo sob reduções em log-espaço. Realmente, todos os problemas NP-completo conhecidos atualmente permanecem NP-completo até sob reduções mais fracas. É sabido, porém, que reduções AC⁰ definem uma classe menor do que as reduções em tempo polinomial.

Erros comuns

Os erros a seguir são bastante comuns.

• "Problemas NP-completo são os problemas mais difíceis conhecidos." Uma vez que problemas NP-completo estão em NP, seu tempo de execução é no máximo exponencial. Porém, alguns problemas requerem mais tempo, como por exemplo a aritmética de Presburger.
• "Problemas NP-completo são difíceis porque existem diferentes soluções." De um lado, existem vários problemas que possuem um espaço de solução grande, mas podem ser resolvidos em tempo polinomial. Do outro lado, existem problemas NP que no máximo uma solução que é NP-difícil sob redução em tempo polinomial aleatória.
• "Resolver problemas NP-completo requerem tempo exponencial." Primeiramente, isso implicaria P ≠ NP, que ainda é uma questão não resolvida. Além disso, alguns problemas NP-completo efetivamente possuem algoritmos que rodam em tempo superpolinomial, porém subexponencial.
• "Todas as instâncias de problemas NP-completo são difíceis" Geralmente algumas instâncias, ou quase todas, podem ser facilmente resolvidas em tempo polinomial

Ver também

• NP (complexidade)
• P versus NP

Bibliografia

• 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.
• Sipser, Michael, Introdução à Teoria da Computação, 2007, Tradução da 2ª edição norte-americana por Ruy José Guerra Berretto de Queiroz.

Ligações externas

• Perguntas e respostas sobre a classe NP-completo;