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

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

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.

Invitez un.e scientifique de l’UMONS dans votre classe

Cet exposé vous est proposé dans le “Catalogue des exposés scientifiques” parmi plus d’une centaine de présentations. Ces exposés sont gratuits et conçus pour enrichir votre enseignement en illustrant des points clés du cours. Le concept est simple : invitez une chercheuse ou un chercheur de l’UMONS dans votre classe pour une présentation captivante sur l’un de ses sujets favoris. En réservant cet exposé, vous assurez un moment mémorable de transmission du savoir à vos élèves !