Le 6 aout 2010, un chercheur Indien de 39 ans a apporté des éléments (une preuve de plus de 100 pages encore en cours de vérification, avec semble-t-il des doutes à ce stade) d’une démonstration de l’un des problèmes les plus importants des mathématiques algorithmiques : P <>NP – c’est à dire : existe-t-il des problèmes pour lesquels il est facile de vérifier si une solution convient, mais très difficile de trouver une solution.


Pour donner une image plus romantique : faut-il les mêmes capacités, et éventuellement un peu de méthode, pour apprécier une symphonie de Mozard ou « l’Etre et le Néant » et pour les écrire ?


P désigne les problèmes dont les solutions peuvent être systématiquement trouvées dans un temps « court » par rapport à la longueur du problème. Par exemple, trier les éléments d’une liste de taille N peut se faire en un temps inférieur à N^2 (il suffit par exemple de parcourir la liste pour chercher les plus petit, puis de parcours le reste de la liste pour cherche le 2e plus petit, etc…).

NP désigne les problèmes pour lesquels il n’existe pas de méthode systématique permettant de les résoudre en un temps « court » (il leur faut un temps exponentiel avec la taille du problème, c’est à dire qu’il devient très rapidement trop long à résoudre, même pour un ordinateur), alors qu’il est possible de vérifier si une solution est la bonne en un temps court. Par exemple, savoir dans quel ordre mettre des valises de tailles différentes pour remplir le plus possible le coffre d’une voiture est un problème difficile : à part essayer toutes les solutions, il n’existe pas de méthode simple assurant un succès rapide dans tous les cas. C’est compliqué  avec 10 valises, très difficile avec 100.000 valises.

Pour savoir si un problème est dans NP, il ne suffit pas d’avoir du mal à trouver une solution : par exemple, la résolution du Rubiks Cube est difficile pour beaucoup de personnes (alors qu’il est très simple de voir s’il a été résolu ou non), mais il existe pourtant des solutions simples et automatisables pour le résoudre. Les chercheurs qui se sont penché sur ces questions ont ainsi identifié un ensemble de problèmes « NP-complets », à la fois difficiles à résoudre, et tels que, si l’un d’entre eux était résolu (c’est à dire si une méthode simple et systématique de résolution était trouvée), alors une méthode simple pour chacun des problèmes « NP » pourrait en être déduite.

Si P n’est pas égal à NP, celà signifie qu’il existera des problèmes dont la solution est facile à vérifier mais pour lesquels personne ne trouvera jamais une solution simple pour les résoudre. Actuellement, on connait actuellement des tas de problèmes durs à résoudre, mais personne n’est sur – à moins que la démonstration de N = NP soit faite – qu’il existe une méthode simple pour leur trouver une solution. Par exemple : remplir un sac ou un coffre, trouver le parcours le plus court possibles passant par une liste de villes, Tétris, gérer des emplois du temps…

Actuellement, la majorité des scientifiques pense que P <> NP, reste à voir si la démonstration de Vinay Deolalikar tient (celà peut prendre du temps, comme ce fut le cas pour le théorème de Fermat, et nécessiter de compléter la preuve actuellement apportée)… Même dans l’hypothèse inverse il aura confirmé la puissance exceptionnelle de l’Inde dans le domaine informatique, et la force du modèle américain de « chasse aux talents »…

À propos

Dédié à l'analyse des questions économiques, sociales et environnementales de long terme, L'Observatoire du Long Terme se fixe pour objectif de donner davantage de visibilité à ces enjeux dans le débat public. Dans ce contexte, il donne la parole à des contributeurs variés, avec pour seul critère le caractère étayé des arguments présentés.

L'Observatoire est indépendant, ne reçoit aucune aide financière et repose sur le volontariat de ses contributeurs, de son bureau, présidé par Vincent Champain et Bruno Fuchs.

Sur le même sujet

LAISSER UN COMMENTAIRE

S'il vous plaît entrez votre commentaire!
S'il vous plaît entrez votre nom ici

Du même auteur

Simplifier dans la durée

Publié dans Les Echos le 8 février 2024. Le coût de la complexité administrative est estimé à près de 5 points de PIB, et il...

Soyons optimistes pour l’optimisme.

Publié dans Les Echos le 11 janvier 2024 L’année 2023 s’est achevée sur des risques de guerre, de terrorisme, de chômage, de perte de pouvoir...

Victimes de crimes violents : que disent les statistiques?

Les homicides ne sont évidemment qu'une dimension de l'insécurité, mais c'est celle qui se prête le mieux aux comparaisons internationales...Source ici : https://dataunodc.un.org/dp-intentional-homicide-victims (décès...

Interview BFM sur les évolutions de l’IA

https://www.bfmtv.com/economie/replay-emissions/01-business/open-ai-le-retour-de-sam-altman-est-synonyme-de-changements-au-conseil-d-administration-25-11_VN-202311250391.htmlhttps://www.bfmtv.com/economie/replay-emissions/01-business/open-ai-le-retour-de-sam-altman-est-synonyme-de-changements-au-conseil-d-administration-25-11_VN-202311250391.html