Garey-Johnson
De AgregmathKL
Révision de 5 février 2019 à 00:00 par David X (discuter | contributions) (Page créée avec « Un bestiaire de problèmes NP-complets avec des références vers les livres ou articles où les démonstrations de NP-complétude sont faites (sauf pour les problèmes cl... »)
Un bestiaire de problèmes NP-complets avec des références vers les livres ou articles où les démonstrations de NP-complétude sont faites (sauf pour les problèmes classiques comme SAT, 3SAT, VERTEX-COVER, CLIQUE, HAMILTONIAN-CIRCUIT etc. dont les réductions sont présentées directement dans le livre). Par contre, ces preuves ne sont pas très faciles à lire, il vaut peut-être mieux se référer à d'autres ouvrages pour cela.
Mais ce livre fournit une liste impressionnante de potentiels développements (qui rentrent au moins dans la leçon sur la NP-complétude) !
Les problèmes sont rangés dans 12 catégories (théorie des graphes, réseaux, ensembles et partitions et autres). Chaque problème est présenté de la manière suivante :
- Nom du problème - Instance du problème - Question (question fermée car ce sont des problèmes de décision) - Référence (et parfois le nom du problème vers lequel faire la réduction pour montrer la NP-dureté) - Commentaire (souvent des variantes du problèmes ou des choses du genre : "le problème reste NP-complet lorsque l'on restreint les instances à ...")
