21 problèmes NP-complets de Karp

Cet article ne cite pas suffisamment ses sources (décembre 2020).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Les 21 problèmes NP-complets de Karp ont marqué une étape importante de l'histoire de la théorie de la complexité des algorithmes. Ce sont 21 problèmes réputés difficiles de combinatoire et de théorie des graphes qui sont réductibles entre eux. C'est ce qu'a démontré Richard Karp en 1972 dans son article Reducibility Among Combinatorial Problems^[1], de même que leur NP-complétude.

Histoire

Un des plus importants résultats en théorie de la complexité est celui de Stephen Cook, en 1971. Dans son article, il montre le premier problème NP-complet, soit le problème SAT (voir théorème de Cook). C'est cette idée que Karp développe en l'appliquant à des problèmes de combinatoire et de théorie des graphes.

Les problèmes

Les 21 problèmes sont organisés en indentations de façon à indiquer la direction de la réduction servant à prouver leur NP-complétude. Par exemple, le problème du sac à dos a été prouvé NP-complet par une réduction à partir de celui de la couverture exacte.

Le nom anglais original est en lettres capitales.

• SATISFIABILITY : le problème SAT pour les formules en forme normale conjonctive
  • CLIQUE : le problème de la clique (voir aussi le problème de l'ensemble indépendant)
    • SET PACKING : Set packing (empaquetage d'ensemble)
    • VERTEX COVER : le problème de couverture par sommets
      • SET COVERING : le problème de couverture par ensembles
      • FEEDBACK ARC SET : feedback arc set
      • FEEDBACK NODE SET : feedback vertex set
      • DIRECTED HAMILTONIAN CIRCUIT : voir graphe hamiltonien
        • UNDIRECTED HAMILTONIAN CIRCUIT : voir graphe hamiltonien
  • 0-1 INTEGER PROGRAMMING : voir optimisation linéaire en nombres entiers
  • 3-SAT : voir problème 3-SAT
    • CHROMATIC NUMBER : coloration de graphe
      • CLIQUE COVER : partition en cliques
      • EXACT COVER : couverture exacte
        • MATCHING à 3 dimensions : appariement à 3 dimensions
        • STEINER TREE : voir arbre de Steiner
        • HITTING SET : ensemble intersectant
        • KNAPSACK : problème du sac à dos
          • JOB SEQUENCING : séquençage de tâches
          • PARTITION : problème de partition
            • MAX-CUT : problème de la coupe maximum

Voir aussi

Bibliographie

• (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, 1972 (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, lire en ligne), p. 85-103

Articles connexes

• Liste de problèmes NP-complets

Notes et références

• Portail de l'informatique théorique