Voir la source de Garey-Johnson

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 à ...")