Difficulté

Nous allons passer en revue dans la section suivante quelques problèmes classiques d'optimisation combinatoire. Nous les classerons en deux catégories

• Les problèmes faciles : c'est-à-dire ceux qui se résolvent en temps polynomial, autrement dit sans avoir à explorer l'intégralité des solutions.
• Les problèmes difficiles : c'est-à-dire ceux qu'on ne peut résoudre qu'en explorant toutes les solutions. On dit que ces problèmes sont NP-Complets.

La définition ci-dessus est très shématique, tenez-vous en à celle-ci pour le moment, un cours sera ultérieurement consacré à l'etude des problèmes NP-Complets.