14 mai 2009
La notion de problème NP-complet a connu un succès extraordinaire dès son introduction au début des années 1970. Très rapidement, des centaines puis probablement des milliers de problèmes NP-complets ont été identifiés. Aujourd’hui, même si la preuve de NP-complétude d’un nouveau problème peut parfois présenter des difficultés techniques non négligeables, cette notion est utilisée de manière quasiment routinière pour justifier l’absence d’algorithme polynomial pour des problèmes issus de pratiquement tous les domaines de la science et de la technologie.
Malheureusement, tous ces résultats ne reposent pas sur une base bien solide puisqu’on ne sait pas démontrer que les problèmes NP-complets n’admettent pas d’algorithme polynomial. En effet, près de 40 ans après son introduction le problème “P=NP ?” reste largement ouvert.
Sans prétendre à l’exhaustivité, je ferai un petit historique de cette question et je présenterai quelques unes des approches qui ont été proposées pour aborder le problème “P=NP ?” et des problèmes voisins.
Pascal Koiran (ENS Lyon)
