21 problemas NP-completos de Karp - Karp's 21 NP-complete problems

Na teoria da complexidade computacional , os 21 problemas NP-completos de Karp são um conjunto de problemas computacionais que são NP-completos . Em seu artigo de 1972, "Reducibility Between Combinatorial Problems", Richard Karp usou o teorema de Stephen Cook de 1971 de que o problema de satisfatibilidade booleana é NP-completo (também chamado de teorema de Cook-Levin ) para mostrar que há um tempo polinomial muitos-um redução do problema de satisfatibilidade booleana para cada um dos 21 problemas computacionais combinatórios e teóricos de grafos , mostrando assim que são todos NP-completos. Essa foi uma das primeiras demonstrações de que muitos problemas computacionais naturais que ocorrem em toda a ciência da computação são computacionalmente intratáveis , e isso despertou o interesse no estudo de NP-completude e do problema P versus NP .

Os problemas

Os 21 problemas de Karp são mostrados abaixo, muitos com seus nomes originais. O aninhamento indica a direção das reduções usadas. Por exemplo, a mochila mostrou ser NP-completa ao reduzir a capa exata para a mochila .

• Satisfatibilidade : o problema de satisfatibilidade booleana para fórmulas na forma normal conjuntiva (muitas vezes referida como SAT)
  • Programação inteira 0-1 (uma variação na qual apenas as restrições devem ser satisfeitas, sem otimização)
  • Clique (veja também o problema dos conjuntos independentes )
    • Definir embalagem
    • Capa de vértice
      • Cobertura definida
      • Conjunto de nós de feedback
      • Conjunto de arco de feedback
      • Circuito de Hamilton direcionado (nome de Karp, agora geralmente chamado de ciclo de Hamiltoniano direcionado )
        • Circuito de Hamilton não direcionado (nome de Karp, agora geralmente chamado de ciclo hamiltoniano não direcionado )
  • Satisfação com no máximo 3 literais por cláusula (equivalente a 3-SAT)
    • Número cromático (também chamado de problema de coloração do gráfico )
      • Tampa da Clique
      • Capa exata
        • Set de acerto
        • Árvore Steiner
        • Correspondência tridimensional
        • Mochila (a definição de Mochila de Karp é mais próxima da soma do Subconjunto )
          • Sequenciamento de trabalhos
          • Partição
            • Corte máximo

Com o passar do tempo, descobriu-se que muitos dos problemas podem ser resolvidos de forma eficiente se restritos a casos especiais, ou podem ser resolvidos dentro de qualquer porcentagem fixa do resultado ideal. No entanto, David Zuckerman mostrou em 1996 que cada um desses 21 problemas tem uma versão de otimização restrita que é impossível aproximar dentro de qualquer fator constante a menos que P = NP, mostrando que a abordagem de Karp para redução generaliza para um tipo específico de redução de aproximabilidade. Observe, entretanto, que eles podem ser diferentes das versões de otimização padrão dos problemas, que podem ter algoritmos de aproximação (como no caso do corte máximo).

Veja também

• Lista de problemas NP-completos

Notas

Referências

• Stephen Cook (1971). "A complexidade dos procedimentos de prova de teorema" . Proc. 3º Simpósio Anual da ACM em Teoria da Computação (STOC) . pp. 151–158. doi : 10.1145 / 800157.805047 . S2CID   7573663 .
• Richard M. Karp (1972). "Redutibility Between Combinatorial Problems" (PDF) . Em RE Miller; JW Thatcher; JD Bohlinger (eds.). Complexidade de Computações Computacionais . Nova York: Plenum. pp. 85–103. doi : 10.1007 / 978-1-4684-2001-2_9 . ISBN   978-1-4684-2003-6 .
• Zuckerman, David (1996). "Sobre versões inadequadas de problemas NP-completos" . SIAM Journal on Computing . 25 (6): 1293-1304. doi : 10.1137 / S0097539794266407 . [1]