Le casse-tête qui a bloqué les informaticiens pendant 80 ans

Imagine un voyageur qui doit visiter 10 villes et revenir chez lui en empruntant le chemin le plus court possible. Simple ? Non. Avec 10 villes, il existe déjà 3,6 millions de trajets différents à comparer. Avec 20 villes, c'est l'infini. Ce problème mathématique apparemment enfantin s'appelle le problème du voyageur de commerce, et il fascine les informaticiens depuis les années 1930. Ses applications ? Partout : optimiser les livraisons, organiser les réseaux électriques, ou même cartographier les gènes. Les meilleurs esprits ont compris qu'aucun algorithme au monde ne peut le résoudre parfaitement en temps raisonnable. Un problème simple en apparence, mathématiquement impossible en réalité.