Aller au contenu

21 problèmes NP-complets de Karp

Un article de Wikipédia, l'encyclopédie libre.

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[1]. C'est ce qu'a démontré Richard Karp en 1972 dans son article Reducibility Among Combinatorial Problems[2], de même que leur NP-complétude.

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)[3]. 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

[modifier | modifier le code]

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.

Notes et références

[modifier | modifier le code]
  1. Thomas Cormen, Charles Leiserson, Ronald Rivest et Clifford Stein (trad. Georges-Louis Kocher), Introduction à l'algorithmique [« Introduction to algorithms »], Paris, Dunod, , 2e éd. (1re éd. 1990), 1146 p. (ISBN 2-10-003922-9), chap. 34 (« NP-complétude »), p. 986
  2. Karp 1972.
  3. (en) Stephen A. Cook, The complexity of theorem-proving procedures, ACM Press, , 151–158 p. (ISBN 9781450374644, DOI 10.1145/800157.805047 Accès libre, S2CID 7573663)

Bibliographie

[modifier | modifier le code]

Articles connexes

[modifier | modifier le code]