Le casse-tête numéro un de l’informatique : P=N ou P ≠ NP ?

Exposé dans les écoles

Calendrier Du 1 septembre 2023 au 30 juin 2025

Durée : 1 x 50 min

Retour à l'activité Catalogue des exposés scientifiques

Les informaticiens sont convaincus qu’il faut un temps de calcul énorme (des heures, journées, années, siècles) pour résoudre certains problèmes dont l’énoncé est pourtant très simple. Un exemple est le problème du voyageur de commerce : étant donné une liste de villes, et des distances entre toutes les paires de villes, existe-t-il un tour qui visite chaque ville une et une seule fois et qui est plus court qu’une longueur maximale donnée ? Tous les algorithmes connus pour ce problème utilisent un temps exponentiel : ces méthodes consomment un temps de calcul qui augmente de façon exponentielle par rapport au nombre de villes. Aujourd’hui, beaucoup de scientifiques sont convaincus qu’il n’existe pas d’algorithme plus efficace pour ce problème, mais personne n’arrive à prouver mathématiquement cette conviction. Pourtant, si quelqu’un trouve une telle preuve, il sera récompensé par un prix d’un million de dollars…

Exposé proposé par Jef Wijsen.