21 problèmes NP-complets de Karp

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 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