NP-Completude e Reduções

Um problema NP-completo é um dos mais difíceis na classe NP, no sentido de que todo problema NP se reduz a ele eficientemente, de modo que resolver rapidamente qualquer problema NP-completo resolveria todos eles.

Definition

Um problema é NP-completo se ele pertence a NP e todo problema em NP se reduz a ele por uma redução em tempo polinomial; tais problemas são os membros maximamente difíceis de NP, equivalentes entre si até uma transformação eficiente.

Scope

Este tópico abrange a classe NP de problemas verificáveis em tempo polinomial, reduções muitos-para-um em tempo polinomial, o teorema de Cook-Levin que estabelece a satisfatibilidade como NP-completa, o catálogo de Karp de problemas combinatórios NP-completos e a metodologia de provar que novos problemas são NP-completos por redução a partir de problemas conhecidos.

Core questions

• O que significa para um problema estar entre os mais difíceis em NP?
• Como o teorema de Cook-Levin identifica um primeiro problema NP-completo?
• Como as reduções são usadas para provar que um novo problema é NP-completo?
• Por que a NP-completude de um problema tem implicações para milhares de outros?

Key theories

Teorema de Cook-Levin

A satisfatibilidade booleana é NP-completa porque a computação de qualquer verificador em tempo polinomial pode ser codificada como uma instância de satisfatibilidade, fornecendo o problema completo fundamental a partir do qual outros são derivados.

Reduções de Karp e a rede de problemas NP-completos

Karp mostrou que vinte e um problemas naturais, desde coloração de grafos até o problema de decisão do caixeiro viajante, são NP-completos por reduções em tempo polinomial, lançando a prática de estabelecer a dificuldade através de uma rede crescente de reduções.

Clinical relevance

A NP-completude é o diagnóstico prático da intratabilidade: uma vez que um problema de agendamento, logística, design ou verificação é demonstrado como NP-completo, os engenheiros param de procurar um algoritmo exato garantidamente rápido e recorrem a algoritmos de aproximação, heurísticas, resolvedores de programação inteira ou restrições que tornam o problema tratável.

History

Cook provou a satisfatibilidade como NP-completa em 1971, e Levin obteve independentemente resultados equivalentes na União Soviética. Em 1972, Karp demonstrou vinte e um problemas NP-completos adicionais, revelando a ubiquidade do fenômeno e tornando a NP-completude a ferramenta central para diagnosticar a dificuldade computacional.

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp

Seminal works

• cook1971
• karp1972

Frequently asked questions

O que significa NP?

NP significa tempo polinomial não determinístico. Equivalentemente, um problema está em NP se uma solução proposta pode ser verificada em tempo polinomial, mesmo que encontrá-la pareça difícil. A rota do caixeiro viajante abaixo de um determinado comprimento é fácil de verificar uma vez dada, mas aparentemente difícil de descobrir.

Como se prova que um novo problema é NP-completo?

Você mostra duas coisas: que o problema está em NP, de modo que as soluções candidatas são verificáveis rapidamente, e que algum problema NP-completo conhecido se reduz a ele em tempo polinomial. A redução transfere a dificuldade conhecida, colocando o novo problema entre os mais difíceis em NP.