Les 21 problèmes NP-complets de Karp - Karp's 21 NP-complete problems

Dans la théorie de la complexité de calcul , les 21 problèmes NP-complets de Karp sont un ensemble de problèmes de calcul qui sont NP-complets . Dans son article de 1972, "Reductibility Among Combinatorial Problems", Richard Karp a utilisé le théorème de Stephen Cook de 1971 selon lequel le problème de satisfiabilité booléenne est NP-complet (également appelé théorème de Cook-Levin ) pour montrer qu'il existe un temps polynomial plusieurs-un réduction du problème de satisfiabilité booléenne à chacun des 21 problèmes de calcul combinatoires et théoriques de graphes , montrant ainsi qu'ils sont tous NP-complets. Ce fut l'une des premières démonstrations que de nombreux problèmes de calcul naturels se produisant tout au long de l' informatique sont insolubles par le calcul , et cela a suscité l'intérêt pour l'étude de l'exhaustivité des NP et du problème P versus NP .

Les problèmes

Les 21 problèmes de Karp sont présentés ci-dessous, beaucoup avec leurs noms d'origine. L'imbrication indique le sens des réductions utilisées. Par exemple, Knapsack s'est avéré être NP-complet en réduisant la couverture exacte à Knapsack .

• Satisfiabilité : le problème de satisfiabilité booléenne pour les formules sous forme normale conjonctive (souvent appelée SAT)
  • Programmation de 0 à 1 entier (Variation dans laquelle seules les restrictions doivent être satisfaites, sans optimisation)
  • Clique (voir aussi problème d'ensemble indépendant )
    • Set emballage
    • Couverture Vertex
      • Ensemble de couverture
      • Ensemble de nœuds de rétroaction
      • Jeu d'arc de rétroaction
      • Circuit Hamilton dirigé (nom de Karp, maintenant généralement appelé cycle hamiltonien dirigé )
        • Circuit Hamilton non dirigé (nom de Karp, maintenant généralement appelé cycle hamiltonien non dirigé )
  • Satisfabilité avec au plus 3 littéraux par clause (équivalent à 3-SAT)
    • Nombre chromatique (également appelé problème de coloration de graphes )
      • Couverture de clique
      • Couverture exacte
        • Jeu de frappe
        • Arbre Steiner
        • Correspondance en 3 dimensions
        • Knapsack (la définition de Karp de Knapsack est plus proche de la somme des sous-ensembles )
          • Séquençage des tâches
          • Cloison
            • Coupe max

Au fil du temps, on a découvert que de nombreux problèmes peuvent être résolus efficacement s'ils sont limités à des cas particuliers, ou peuvent être résolus dans un pourcentage fixe du résultat optimal. Cependant, David Zuckerman a montré en 1996 que chacun de ces 21 problèmes a une version d'optimisation contrainte qu'il est impossible d'approximer dans un facteur constant à moins que P = NP, en montrant que l'approche de Karp à la réduction se généralise à un type spécifique de réduction d'approximabilité. Notez cependant que celles-ci peuvent être différentes des versions d'optimisation standard des problèmes, qui peuvent avoir des algorithmes d'approximation (comme dans le cas de la coupe maximale).

Voir également

• Liste des problèmes NP-complets

Remarques

Les références

• Stephen Cook (1971). "La Complexité des Procédures de Preuve de Théorème" . Proc. 3e Symposium annuel de l'ACM sur la théorie de l'informatique (STOC) . 151-158. doi : 10.1145 / 800157.805047 . S2CID   7573663 .
• Richard M. Karp (1972). "Réductibilité parmi les problèmes combinatoires" (PDF) . Dans RE Miller; JW Thatcher; JD Bohlinger (éd.). Complexité des calculs informatiques . New York: Plénum. 85–103. doi : 10.1007 / 978-1-4684-2001-2_9 . ISBN   978-1-4684-2003-6 .
• Zuckerman, David (1996). "Sur les Versions Unapproximables de Problèmes NP-Complets" . Journal du SIAM sur l'informatique . 25 (6): 1293-1304. doi : 10.1137 / S0097539794266407 . [1]