Les 7 problèmes mathématiques du millénaire. 1/2

P NP Probleme

En 2000, l’institut de mathématiques Clay donne la liste de 7 problèmes mathématiques du millénaire.

Il propose de donner 1 million de dollars à la personne qui démontrera l’un de ces problèmes.

En 2003, l’un de ces problèmes a été résolus, il s’agit de la conjecture de Poincaré. 6 millions restent encore en jeu, si vous vous sentez de devenir le plus grand mathématicien de ce début du XXIème siècle.

Pour chacun des problèmes, il s’agit en fait d’hypothèses émises par des mathématiciens mais qui n’ont jamais pu le démontrer. Si certains de ces 7 problèmes sont résolus, cela pourrait à jamais l’histoire des mathématiques et de l’informatique.

Dans cet article, je vous présente 2 des 7 problèmes du millénaire.

Problème 1 : Hypothèse de Riemann

Les nombres premiers sont des nombres divisibles par 1 et lui-même. On connait les premiers nombres tels que 2,3,5,7,11,…

Pour les derniers nombres premiers avant 100, ce sont 71, 73, 79, 83, 89, et 97.

On se rend compte qu’il n’y a aucune suite logique. Pour savoir si un nombre est premier ou pas, il faut tester ce nombre avec tous les nombres plus petits que lui-même et qui pourraient le diviser.

Mais Riemann s’est rendu compte que les nombres premiers suivent la même suite que la suite suivante, nommée Riemann Zela :

  ζ(s) = 1 + 1/2s + 1/3s + 1/4s +…

L’hypothèse de Riemann est de dire que toutes les solutions de l’équation ζ(s) = 0 se représentent par une ligne droite verticale.

220px-Riemann_zeta_function_absolute_value
Représentation de la fonction Zeta de Riemann (source : Wikipedia)

Cette hypothèse est vérifié pour les 10 milliards premières solutions. L’objectif de cette démonstration est de le montrer pour toutes les solutions. Si vous réussissez, il y a 1 million d’euros à la clé !

Ainsi, on pourrait prédire les nombres premiers sans avoir à les deviner.

Problème 2 : Le problème P = NP

Le problème le plus intéressant de ces 7 énigmes : il est considéré comme résoluble par un non-spécialiste et le fait de le démontrer pourra engendrer des conséquences inimaginables dans le domaine de l’informatique .

Un problème de type P est facilement démontrable par ordinateur. Par exemple, il est capable de calculer le valeur de x dans l’équation x-2 = 4. L’ordinateur est aussi capable de vérifier qu’une valeur proposé est vraie ou fausse. Par exemple, si on dit que x=7, l’ordinateur va infirmer car 7-2 = 5, tandis que si on lui donne la bonne réponse, 6 , il va confirmer que c’est le bon résultat.

Un problème de type NP n’est pas démontrable par l’ordinateur mais est vérifiable. Le problème le plus connu est celui du voyageur. Vous partez en vacances et souhaitez aller dans 20 villes puis revenir chez vous. Quel chemin choisir pour effectuer la plus courte distance ?
Même le plus grand ordinateur qui soit n’est pas capable de trouver rapidement le plus court chemin.
Par-contre, il est capable de vérifier que l’un des chemins proposé est une solution : il suffit de montrer que la route que vous avez proposée passe par les 20 villes.

En fait, ce que pourrait faire l’ordinateur c’est de calculer 1 par 1 la distance des différents chemins. Ça peut-être fait pour 3 villes par exemple, il aura alors 1 seul choix possible. En partant du point A, l’ordinateur va au point B puis au point C. Il peut partir de A en passant d’abord par C puis par B mais le chemin est identique : partir de Paris et aller à Marseille puis Lyon ou Lyon puis Marseille revient au-même au niveau des distances.

Pour 4 villes, on a trois possibilités : ABCDA, ABDCA, ADBCA.

Problème du voyageur
Problème du voyageur sur 4 villes

Le problème se complique de plus en plus.

Pour notre problème de 20 villes, il y a 60 000 000 000 000 000 soit 6*10^16.

Tenez-vous bien. En calculant 1 chemin par seconde, l’ordinateur devra prendre 190 millions d’années pour tester toutes les possibilités de ce problème qui semble pourtant simple.

Revenons à notre problème P = NP.

On sait qu’un problème démontrable de classe P (par exemple, x-2=4) est facilement vérifiable (en proposant x égal à quelque chose, on sait si la solution est correcte ou pas).

Par-contre, un problème de classe NP est facilement vérifiable (en effet, la route passe bien par les 20 villes), mais pas facilement démontrable (il faut tout tester 1 par 1).

800px-P_np_fr.svg
A gauche, on représente graphiquement le cas où P est différent de NP. A droite, P serait égal à NP.

L’objectif est donc de démontrer soit qu’un problème facilement vérifiable est facilement démontrable (P=NP) ou bien encore, d’expliquer qu’un problème facilement vérifiable n’est pas facilement démontrable (P différent de NP).

Les enjeux sont nombreux :

Si on arrive à démontrer que P=NP, alors il sera possible de trouver une solution rapidement à notre problème de voyageur. Par-contre, les cryptages informatiques ne serviront plus à rien. En effet, les données sont cryptées en prenant en compte qu’il est impossible de casser les codes (à moins de vérifier 1 code par seconde comme pour le problème du voyageur). Si P=NP, alors on saura qu’il est possible de décrypter les codes informatiques et les plus malicieux travailleront sur ce projet pour déchiffrer les chiffrements existants.


Vous voulez plus d’articles ?

Suivez SinstruireFR sur Facebook et Twitter.

2 commentaires

  1. benkour Répondre

    J’ai résolut l’équation de quantitaté de mouvement de Naviers Sotkes

  2. benkour Répondre

    pardon pour cette faute d’orthographe je voulais dire l’équation de quantité de mouvement de Navier Stokes

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *