[PEAC/CHRONIQUES SCIENTIFIQUES] Voulez-vous tenter de gagner un million de dollars ?

Dans le cadre du parcours d'éducation artistique et culturelle (PEAC) mis en place depuis l'an dernier, un nouvel atelier s'est créé à la rentrée : la rédaction de chroniques scientifiques par nos élèves, avec le soutien de deux professeurs des sciences physiques. Deuxième chronique consacrée à une question aussi mystérieuse que alléchante, proposée par l'un de nos élèves en première.

« P = NP » fait partie des problèmes du millénaire, les sept problèmes mathématiques mis à prix à 1 million de dollars par l’institut Clay, un institut de mathématiques offrant des fonds aux chercheurs afin de diffuser les connaissances mathématiques dans le monde. Il serait essentiel pour les mathématiciens de résoudre ces problèmes avant l’an 3 000.

Résoudre ce problème consisterait à prouver que l’ensemble des problèmes P – problèmes faciles à résoudre et faciles à vérifier – serait équivalent à l’ensemble des problèmes NP – problèmes difficiles à résoudre mais facilement vérifiables, c’est-à-dire que les problèmes difficiles à résoudre pourraient devenir des problèmes faciles à résoudre. Cela permettrait de grandes avancées dans la cryptologie – protection des comptes bancaires, etc., les mathématiques, la vitesse des algorithmes, …

Schéma : http://www.fredtechnocollege.org/algorithmes-2/

Un algorithme est la description d’une suite d’instructions aboutissant à un résultat. Par exemple, une recette de cuisine ou un plan de bricolage sont des algorithmes.

La complexité d’un algorithme est définie par une fonction de x, avec x qui correspond au nombre d’instructions nécessaires pour effectuer la tâche. Plus il y a d’instructions à réaliser plus la complexité est élevée et plus le programme met de temps à finir la tâche (par analogie, plus il y a d’étapes dans une recette plus elle est longue à réaliser).

Il existe plusieurs types de complexité :

Illustration : Représentation graphique de différentes fonctions (linéaire : https://www.maths-cours.fr/methode/tracer-fonctions-affines-lineaires ; carré : https://www.maths-cours.fr/cours/fonction-carre ; exponentielle : https://fr.wikipedia.org/wiki/Fonction_exponentielle

Prenons un être humain. Lui demander de trouver la plus grande valeur dans une liste ne lui sera pas compliqué. Lui donner une valeur et lui demander de vérifier si le nombre proposé est le plus grand de la liste non plus : c’est donc un problème P.

À l’inverse, lui demander de résoudre un sudoku lui posera quelques difficultés, mais en lui soumettant une proposition du sudoku déjà résolu, il n’aura pas de problèmes à vérifier si la proposition est correcte ou non : c’est donc un problème NP.

Par exemple on pourrait modéliser le nombre de calculs en fonction d’une difficulté x comme :

Il existe un troisième groupe, les problèmes « NP-difficile », qui sont difficiles à résoudre et difficiles à vérifier.

Il existe deux méthodes : la plus simple serait de trouver au moins un contre-exemple à P = NP, c’est-à-dire un problème où P ≠ NP, les deux ensembles ne pourront donc pas être identiques. Cependant, il existe une infinité de problèmes, il est donc impossible de tous les tester un par un.

La seconde solution consisterait à résoudre le problème SAT (problème de satisfaisabilité), une sorte de problème universel qui peut représenter n’importe quel problème NP. S’il est soluble comme les problèmes P, cela prouvera que P = NP. Et, inversement, si SAT n’est pas soluble comme un problème P, alors on prouvera que P ≠ NP. Si ce problème peut être résolu rapidement, tous les problèmes NP le seront aussi.

Schéma : Ensembles P et NP d'après Techno Science (https://www.techno-science.net/actualite/np-conjecture-000-000-partie-denouee-N21607.html)

Prouver que P = NP permettrait de prouver que tous les problèmes NP seraient solubles avec des algorithmes simples et permettraient donc d’améliorer la vitesse des programmes informatiques.

À l’inverse, prouver que P ≠ NP assurerait la sécurité des comptes en banque car il n’existerait pas d’algorithme pour les hacker rapidement. Des pistes pour accélérer les algorithmes seraient quand même trouvées et la personne qui aura résolu le problème gagnera un million de dollars !