21 problèmes NP-complets de Karp
De Wikipedia, l'encyclopédie encyclopedia
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.
Cet article ne cite pas suffisamment ses sources ().
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 ?