21/10/2018

Guérison du cancer, sécurité bancaire en péril, addiction à «Candy Crush» : a-t-on résolu le problème P = NP ?

P NP.jpgSi vous êtes attentifs et accro aux news de toute provenance, il ne vous aura sans doute pas échappé qu’en août 2017, un mathématicien allemand, Norbert Blum, affirmait avoir résolu le plus célèbre problème ouvert de mathématiques et d'informatique théorique, soit le problème P = NP, concluant par la négative que P n'est pas égal à NP. La communauté, qui se penche depuis sur la question et les 38 pages de sa démonstration, n'a pas encore rendu son verdict, tout en laissant entendre qu'il y a peut-être une erreur dans son raisonnement. C'est que l'enjeu est énorme. Il y a d'abord la récompense d'un million de dollars (décerné par le Clay Mathematics Institute). Et ensuite la renommée mondiale que cette démonstration impliquerait. Le problème P = NP a été énoncé pour la première fois dans les années 70. Il s'agit d'une conjecture dont l'importance est fondamentale dans l'histoire des sciences. Tenter de la présenter n'est pas le plus simple des exercices et j'y serai sans doute moins à l'aise que Siraj Raval, dont voici la chaîne YouTube (https://www.youtube.com/channel/UCWN3xxRkmTPmbKwht9FuE5A), et dont je recommande le visionnement de plusieurs vidéos, comme s'il n'avait déjà pas assez de clics.
De manière caricaturale, on pourrait réduire les définitions de P et NP en affirmant qu’on a d’un côté les problèmes (mathématiques) faciles à résoudre (P) et de l’autre ceux qui ne le sont pas (ou moins) (NP). Les problèmes dits de classe P peuvent en effet être décidés (et résolus) en temps polynomial par une machine de Turing ou apparentée. Donc se décomposer en un algorithme ou une suite de calculs relativement basiques que les ordinateurs peuvent exécuter assez rapidement. Ceux de classe NP (pour «nondeterministic polynomial time») ne peuvent pas être résolus si rapidement. Pire, le nombre de solutions qu’ils comportent pose problème, et ne présupposent pas forcément l’existence d’un algorithme. Prenons un exemple concret, celui de la décomposition d’un nombre entier en facteurs premiers. Facile ? Non, pas si le nombre est trop grand. Car il faut alors tenter de le diviser par tous les facteurs premiers inférieurs, et cela peut prendre un temps infiniment long. Sans algorithme, même les plus puissants des ordinateurs n’en viendraient pas à bout assez vite. Et prendraient parfois jusqu’à plusieurs milliers d’années pour casser le nombre. C’est d’ailleurs sur ce type de clés que repose la sécurité bancaire, vous me suivez ?

carte.jpgLe problème du voyageur de commerce, qui consiste à déterminer le chemin le plus court pour passer dans plusieurs villes une et une seule fois sur un circuit donné, est fréquemment utilisé pour illustrer ce qu’on appelle un problème NP-complet - j’y consacrerai un autre billet prochainement. Ce joli graphe ci-dessus l’illustre et un petit détour par la théorie des graphes est elle aussi au menu d’un billet futur. Dans l’attente, revenons à l’interrogation cruciale mise à prix par le Clay Institute. Et rappelons qu’à l’heure actuelle, on ne sait pas si P = NP, si P ≠ NP ou si l’égalité est non décidable, et cela même si certains chercheurs isolés affirment avoir démontré la chose. En revanche, on sait que P est inclus dans NP. Soit, mais à quoi tout cela mène-t-il ? Si on ramène l’égalité P = NP à une question, on peut la formuler ainsi : lorsqu’une solution à un problème est rapidement vérifiable, peut-elle être rapidement trouvée ? Autrement dit, peut-on trouver en temps polynomial ce que l'on peut prouver en temps polynomial?

Intuitivement, la plupart des mathématiciens pensent que P ≠ NP, et c’est sans doute le cas. Mais si c’était l’inverse, si P = NP était vrai, alors cela changerait la face du monde. En effet, entre autres implications, cela signifierait, en médecine, qu’on pourrait soigner certaines formes de cancer. Si des algorithmes suffisaient à prouver que des problèmes complexes n’étaient que des variantes de problèmes simples (P = NP), une meilleure compréhension du processus conférant leur structure aux protéines permettrait ainsi d’empêcher qu’il ne s’en forme des anormales, et donc à terme freiner, voire stopper la prolifération de certaines catégories de cancer. Le chiffrement des données bancaires, lui, serait sacrément mis à mal, et casser un code de 256-bit (c’est généralement celui qui est utilisé pour vos cartes bancaires) serait assez aisé, du moins si le temps pour décomposer un nombre très grand en facteurs premiers diminuait, ce qu’on peut supposer si P = NP. Même chose pour la protection des données et des informations sur Internet, a priori déjà fragilisées. Il faudrait tout revoir (après un probable krach informatique mondial), d’autant plus que les protocoles de sécurité sur le net reposent tous sur le fait que…  P ≠ NP.

Ce n’est évidemment pas tout. On pourrait alors viser plus haut et tenter de déterminer une partie d’échecs parfaite ou encore résoudre le casse-tête posé par ce jeu addictif et sucré nommé «Candy Crush», qui se pratique aussi bien sur smartphone que derrière un écran : tous deux sont en effet considérés comme des problèmes NP-complets. Pour l’instant, nous en sommes loin. Et comme la solution du problème risque d’être P ≠ NP, toutes ces séduisantes hypothèses risquent bien de s’effondrer comme châteaux de sable.

17:20 Publié dans Mathématiques, Sciences | Lien permanent | Commentaires (3) | |  Facebook | | | |

Commentaires

Passionnant et bravo pour votre sens didactique car pareil sujet à expliquer n’est pas aisé...

Écrit par : Hélène Richard-Favre | 21/10/2018

Répondre à ce commentaire

P=NP

La classe NP est alors l'ensemble des langages L pour lesquels il existe un entier k, et une relation R reconnue en temps polynomial, tel que pour tout w,

{displaystyle win LLeftrightarrow exists y(|y|

Écrit par : NOËL Pierre | 22/10/2018

Répondre à ce commentaire

Coupeurs de langues + coupeurs de commentaires = fascisme. Plus aucun commentaire chez vous.

Écrit par : NOËL Pierre | 24/10/2018

Répondre à ce commentaire

Écrire un commentaire

NB : Les commentaires de ce blog sont modérés.