supposons que vous organisiez des logements pour un groupe de quatre cents étudiants universitaires. L’espace est limité, et seulement une centaine d’étudiants recevront des places dans le dortoir. Pour compliquer les choses, le doyen vous a fourni une liste de paires d’étudiants incompatibles et a demandé qu’aucune paire de cette liste n’apparaisse dans votre choix final., Ceci est un exemple de ce que les informaticiens appellent un NP-problème, car il est facile de vérifier si un choix donné de cent étudiants proposés par un collègue est satisfaisant (c.-à-d., aucune paire tirée de la liste de votre collègue apparaît également sur la liste du Bureau du Doyen), mais la tâche de générer une telle liste à partir de zéro semble être si difficile qu »être complètement impraticable. En effet, le nombre total de façons de choisir cent étudiants parmi les quatre cents candidats est supérieur au nombre d’atomes dans l’univers connu!, Ainsi, aucune civilisation future ne pourrait jamais espérer construire un supercalculateur capable de résoudre le problème par la force brute; c’est-à-dire en vérifiant toutes les combinaisons possibles de 100 étudiants. Cependant, cette difficulté apparente ne peut que refléter le manque d’ingéniosité de votre programmeur. En fait, l’un des problèmes en suspens en informatique est de déterminer s’il existe des questions dont la réponse peut être vérifiée rapidement, mais qui nécessitent un temps incroyablement long à résoudre par une procédure directe., Des problèmes comme l’un de ceux énumérés ci-dessus semblent être de ce genre, mais jusqu’à présent personne n’a réussi à prouver que l’un d’eux sont vraiment si dur qu’ils apparaissent, c’est à dire, qu’il n’y a vraiment aucun moyen possible de générer une réponse avec l’aide d’un ordinateur. Stephen Cook et Leonid Levin ont formulé indépendamment le problème P (c’est-à-dire facile à trouver) par rapport au problème NP (c’est-à-dire facile à vérifier) en 1971.
crédit D’Image: à gauche, Stephen Cook de Jiří Janíček (recadrée). CC BY-SA 3.0