Ce cours propose une introduction à la théorie de la complexité des problèmes d'’optimisation combinatoire (théorie de la NP-complétude).
L'’objectif est de donner un sens et des éléments de réponse à la question suivante : dans quelle mesure peut-on dire qu'’un problème est intrinsèquement difficile à résoudre d’'un point de vue algorithmique ?
Les concepts abordés sont les suivants : machines de Turing (déterministes ou non déterministes), problèmes de décision, liens entre problèmes d’'optimisation et problèmes de décision, classes P et NP, transformations polynomiales, transformations de Turing, problèmes polynomiaux, NP-complets, NP-difficiles, hiérarchie polynomiale.