Partager cet article

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

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

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.

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.»

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...

En poursuivant votre navigation sur ce site, vous acceptez l’utilisation de cookies pour réaliser des statistiques de visites, vous proposer des publicités adaptées à vos centres d’intérêt et nous suivre sur les réseaux sociaux. > Paramétrer > J'accepte