Certains problèmes combinatoires sont dits NP-Complets, cela signifie qu'il n'est possible de les résoudre qu'en passant par une recherche exhaustive dans l'ensemble des solutions, ce qui est concrètement irréalisable. Le but de ce cours est de vous montrer comment reconnaître qu'un problème est NP-Complets, et comment le prouver.
Le chapitre de [2] sur la NP-Complétude fournit un exposé clair de la théorie de la complexité, mais utilisant des concepts de calculabilité que je n'utilise pas dans ce cours. La lecture de ce chapitre ne pourra cependant que vous être bénéfique. L'ouvrage [8] est la bible de la théorie de la complexité. Bien qu'il ne soit disponible qu'en anglais et relativement difficile à se procurer, la théorie y est expliquée de façon claire, détaillée, et sans excès de formalisme.