Pascal Koiran – Près de 40 ans après le théorème de Cook, où en est la complexité algorithmique
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…
