Société

P = NP ou P ≠ NP, le problème de maths à un million de dollars

Temps de lecture : 2 min

Il fait parti des sept problèmes du prix du millénaire proposés par l’Institut de mathématiques Clay en 2000, et n'a toujours pas été résolu.

Le problème reste pour l'heure irrésolu | Quinn Dombrowski via Flickr CC License by CC
Le problème reste pour l'heure irrésolu | Quinn Dombrowski via Flickr CC License by CC

Dans la jungle des problèmes mathématiques difficiles ou impossibles à résoudre, on a distingué il y a bien longtemps plusieurs catégories. Il y a les problèmes de type E, dont la résolution pourrait prendre des millions ou des milliards d’années de calculs. Les types P, que l’utilisation d’un ordinateur un peu puissant devrait permettre de résoudre, et les NP, considérés comme intermédiaires.

Il est extrêmement difficile de résumer la différence entre la catégorie P et la catégorie NP, mais cette citation de Wikipedia n’est pas la moins claire:

«Très schématiquement, il s'agit de déterminer si le fait de pouvoir vérifier rapidement une solution à un problème implique de pouvoir la trouver rapidement; ou encore, si ce que nous pouvons trouver rapidement lorsque nous avons de la chance peut être trouvé aussi vite par un calcul intelligent.»

Parmi les sept problèmes du prix du millénaire proposés par l’Institut de mathématiques Clay en 2000, lequel promet sept fois un million de dollars à qui saura les résoudre, il y a la question suivante: a-t-on P = NP ou P ≠ NP? Trouver la solution à ce problème, c’est un peu comme mettre la main sur la clé de l’univers: si P = NP, alors la résolution de tous les autres problèmes posés par l’Institut Clay deviendrait soudain évidente; et si jamais P ≠ NP, cela aurait pour conséquence que bon nombre de problèmes dont personne n’a encore trouvé la solution sont destinés à rester insolubles pour l’éternité.

«Tout deviendrait moins cher»

Les conséquences sont loin de n’être qu’abstraites, comme l’explique ce podcast de la BBC:

«L’un des effets négatifs qu’aurait la démonstration de P = NP est la totale remise en question de toute forme de sécurité sur internet car cela rendrait déchiffrables toutes les clés de cryptographie. Du côté des effets positifs, tout deviendrait moins cher, car les transports de marchandises d’un point à un autre s’en trouveraient révolutionnés.»

Comme le résume l’une des intervenantes:

«On ne pourrait plus utiliser sa carte bancaire sur Amazon car ses informations pourraient être déchiffrées. Mais les prix seraient vraiment plus bas, et c’est une contrepartie intéressante.»

Inscrivez-vous à la newsletter de SlateInscrivez-vous à la newsletter de Slate

La preuve que les mathématiques sont loin d’être inutiles et qu’elles pourraient même servir à faire la révolution. Souvenez-vous de Mr. Robot...

Newsletters

Le culte de la confiance est-il un piège pour les femmes?

Le culte de la confiance est-il un piège pour les femmes?

Elles doivent être à la fois des mères confiantes et des travailleuses à plein temps qui s'affirment.

Mon Europe à moi: «À quand un Erasmus qui s'adresse vraiment à tous les jeunes?»

Mon Europe à moi: «À quand un Erasmus qui s'adresse vraiment à tous les jeunes?»

L'Union européenne s'est engagée sur un nouveau programme Eramus+ qui devrait s'ouvrir à de nouveaux publics.

«Agitation politique», «lecture de romans»… Au XIXe siècle, on internait les femmes un peu trop émancipées

«Agitation politique», «lecture de romans»… Au XIXe siècle, on internait les femmes un peu trop émancipées

Dans son livre «Le Bal des folles», adapté en film, Victoria Mas évoque l'histoire des femmes placées de force à la Salpêtrière. Si les conditions d'internement en hôpital psychiatrique ne sont plus les mêmes aujourd’hui, des problèmes subsistent.

Podcasts Grands Formats Séries
Slate Studio