Choux romanesco, Vache qui rit et intégrales curvilignes

20 septembre 2008

Le roi des nombres premiers

12 978 189...
Non, ce n'est pas le plus long des nombres premiers (surtout que c'est pas un nombre premier), mais le nombre de chiffres nécessaire pour écrire le plus long des nombres premiers, récemment authentifié.

Rappelons-le au cas où : Un nombre premier est un nombre que le ne peut pas écrire comme le produit de deux autres nombres entiers.

Remontons à l'origine...
On date la découverte des nombres premiers aux années 23 000 avant Jésus-Christ, gravés sur un os les 4 nombres premiers 11, 13, 17 et 19.
Quelques années plus tard (vers 300 av J-C), Euclide prouve qu'il y en a une infinité, et depuis, l'humanité n'a pas arrêté de chercher des nombres premiers de plus en plus grands !

Les règles du jeu sont données par l'EFF Cooperative (Une ONG américaine qui défend la liberté d'expression sur internet):
50 000$ pour un nombre premier à au moins 1 000 000 de chiffres
100 000$ pour un nombre premier à au moins 10 000 000 de chiffres
150 000$ pour un nombre premier à au moins 100 000 000 de chiffres
250 000$ pour un nombre premier à au moins 1 000 000 000 de chiffres
Il faut trouver de tels nombres premiers, mais aussi prouver la primalité de tels nombres pour espérer gagner le pactole.

Aujourd'hui, seul GIMPS peut prétendre pouvoir trouver de tels nombres premiers. GIMPS, c'est le Great Internet Mersenne Prime Search, qui utilise internet et de nombreux volontaires pour effectuer tous les calculs nécessaires à la recherche des grands nombres premiers. Si vous voulez faire parti de ces volontaires et, avec de la chance, détenir l'ordinateur qui trouvera un nouveau grand nombre premier, c'est là-bas qu'il faut aller.

Depuis 1996, tous les nouveaux records sont détenus par le projet GIMPS, mais surtout, tous les nombres premiers découverts sont des nombres premiers de Mersenne.
Un nombre Mersenne, c'est un nombre de la forme M_p=2^p-1, avec p un nombre premier.
Par exemple, avec p=7 (premier), on a M₇=2⁷-1=127 (premier)
Tous ces nombres ne sont pas forcément premiers (Avec p=11, on a M₁₁=2047=23×89, donc non premier), mais ce sont les meilleurs candidats pour devenir les plus grands nombres premiers découverts !

Le test de primalité de Lucas-Lehmer
Pour savoir si un nombre n est premier, l'idée de base est de chercher à le diviser par tous les nombres de 2 à n-1. Si aucune de ces divisions ne tombe juste, c'est que n est premier.
Avec un peu plus de subtilité, on peut améliorer cet algorithme en ne testant que le nombre 2 et les nombres impairs de 3 à √n. On peut encore améliorer un tel programme en ne cherchant à diviser n que par les nombres premiers entre 2 et √n (mais cela suppose tous ces nombres premiers déjà connus). On a quand même découvert d'autre algorithmes permettant de tester la primalité d'un nombre de manière plus ou moins efficace...

Mais pour de très grands nombres, de tels algorithmes se révèlent bien trop long à mettre en place... Pr contre, quand on est face à des nombres de Mersenne, la donne est changée. Un test de primalité (celui de Lucas-Lehmer) est particulièrement adapté aux nombres de Mersenne :

Le test est le suivant :
On considère la suite de nombres s_n définie par s_n+1=s_n²-2 avec s₀=4.
Si la division de s_p-2 par M_p est entière, alors M_p est un nombre premier !

Par exemple, le nombre M₅=31 est-il premier ?
On calcule d'abord s₃ :
s₀=4
s₁ = 4²-2 = 14
s₂ = 194
s₃ = 37634
Puisque 37634/31 = 1214 (la division est entière), c'est que M₅ est un nombre premier !

(Bon, on s'en doutait, mais c'était histoire d'utiliser Lucas Lehmer !)
Dans la pratique, on ne va pas s'amuser à calculer explicitement la suite s_n (Les nombres y sont vraiment trop grands), mais c'est tout comme.

Depuis le début de l'humanité, seuls 46 nombres premiers de Mersenne ont été découverts, dont 12 découverts depuis 1996 par le projet Gimps.
Les premiers de ces nombres premiers sont 3 (p=2), 7 (p=3), 31 (p=5) et 127 (p=7), connus depuis l'antiquité.
Au début de l'année 2008, 44 nombres premiers de Mersenne étaient connus (le dernier datant de septembre 2006). Et c'est au cours de l'été 2008 qu'un 45eme fut détecté. Puisque c'était les vacances, il a fallut attendre la rentrée avant de l'authentifier (Tester, avec d'autres ordinateurs, que ce nombre est bien premier). Mais le 6 septembre, un 46eme a été trouvé en Allemagne !

Les deux nouveaux nombres ont été révélés en même temps, après leur authentification (séparément aux USA (13 jours de calculs), en Nouvelle-Zélande (5 jours de calculs) en France et au Canada), le 15 septembre 2008.

Les deux nombres gravés dans l'histoire sont les suivants :

2^{43 112 609}-1
(12 978 189 chiffres)
et
2^{37 156 667}-1
(11 185 272 chiffres)

Mais à quoi ça sert de si grand nombre ?
Essentiellement, à pas grand chose !... Enfin, pour le plaisir de la certitude de la primalité de trèèès grands nombres ! On peut quand même trouver une utilité mathématique aux premiers de Mersenne : les nombres parfaits :

Un nombre parfait est un nombre égal à la somme de ses diviseurs propres (différents de lui). Par exemple, le nombre 6 possède 3 diviseurs : 1, 2 et 3. On a 1+2+3=6, donc 6 est un nombre parfait.
Au IIIe siècle avant Jésus-Christ, Euclide trouve un lien entre les nombres parfaits pairs et les nombres premiers de Mersenne :
Si M_p=2^p-1 est premier, alors n = M_p*(M_p+1)/2 =  (2^p-1)*2^p-1 est un nombre parfait.
Inversement, tous les nombres parfaits pairs peuvent s'écrire de cette façon :

6 =  (2² − 1)2¹ est parfait
28 = (2³ − 1)2² est parfait
496 =  (2⁵ − 1)2⁴ est parfait
8128 =  (2⁷ − 1)2⁶ est parfait

Le plus grand nombre parfait actuellement connu est donc
(2^{43 112 609} − 1)2^{43 112 608}

Et qu'en est il des nombres parfaits impairs ? On vous le dira dès qu'un nombre parfait impair sera découvert... Pour l'instant, on est bien incapable de dire s'il en existe ou pas !

---

Sources :
Le site du projet GIMPS

25 mai 2008

Cousins sexy

Continuons ce petit voyage parmi les nombres premiers, terrain d'aventure et de mystère s'il en est, ou les conjectures les plus simples croisent les théorèmes les plus tordus, où l'on croise des jumeaux, des cousins, des sexy ou des médailes Field !

Les nombres premiers - Les nombres premiers jumeaux
Les nombres premiers cousins - Les nombres premiers sexy

Les nombres premiers jumeaux
Les nombres premiers, on le sait depuis Euclide, sont en nombre infini. Donc, beaucoup trop présent ! Les nombres premiers jumeaux, par contre, sont déjà plus rare.
Un couple de nombre premiers est dit "jumeaux" s'ils sont séparés de 2. Par exemple, (3,5), (5,7), (11,13) ou (17,19) sont des couples de nombres premiers jumeaux.
Comme les nombres premiers, y a t'il un nombre infini de nombres premiers jumeaux ? Grande question, la réponse attend toujours !
Le plus grand couple de jumeaux connu est actuellement 2003663613 × 2¹⁹⁵⁰⁰⁰±1.

A propos de ce problèmes, quelques résultats sont déjà connus, notamment celui de la constante de Brun, quelque peu décevante. La constante de Brun est le nombre B2=1,9021605825..., celui ci est égal à la somme (infinie ?) suivante :

(S'il y a un nombre fini de nombres premiers jumeaux, c'est évident que cette somme est finie ; Dans le cas où ils sont en nombre infinis, cela veut dire que les paires de jumeaux sont de plus en plus espacées, que l'on ajoute à la somme quelque chose de toujours plus petit)

Pourquoi décevante ? Parce que l'on sait d'un autre côté que la somme des inverses des nombres premiers, quand à elle, diverge (est égale à +∞):

Si on avait trouvé que la série des inverses des nombres premiers jumeaux était divergente, on pouvait tout de suite conclure à son infinité... Mais ce n'est pas le cas, et c'est bien dommage !

Les nombres premiers cousins et sexy
Pourquoi séparer les premiers par 2, et pas par 4 ou 6 ? C'est ainsi que sont nés les nombres premiers cousins et les nombres premiers sexy.
Un couple de nombres premiers cousins est un couple de premiers de la forme (p, p+4), un couple de nombres premiers sexy est de la forme (p, p+6) (Et tient son nom du latin "sex" qui signifie 6...)

Les premiers cousins sont (3, 7), (7, 11), (13, 17), (19, 23), (37, 41), les premiers sexy sont (5,11), (7,13), (11,17), (13,19), (17,23), (23,29), (31,37), (37,43). Tout comme pour les nombres premiers jumeaux, on ne sait pas dire s'ils sont ou pas en nombre infinis ; les plus grands nombres premiers sexy connus comptent tout de même 10154 chiffres !
La conjecture de Polignac, qui généralise la conjecture des premiers jumeaux, prétend que pour n'importe quel k pair, il existe une infinités de couples de nombres premiers de la forme (p, p+k). On attend aussi une démonstration pour cette conjecture !

Ce qu'il y a d'intéressant avec les nombres premiers sexy, c'est que non seulement, ils forment des couples, mais également des  triplets ou des quadruplets.  Par exemple, (5,11,17,23) est un quadruplet sexy ! Ce qui est dommage dans cet exemple, c'est qu'il y a le nombre 7, premier, qui se ballade entre 5 et 11. Le plus fort serait de trouver un quadruplet (p, p+6, p+12, p+18) tels que p+2, p+4, p+8 etc. ne soient pas premiers. De tels quadruplets existent, comme par exemple (487, 491, 499, 503). Évidement, on ne sait pas s'ils sont en nombre infini.

Pour un motif donné de "saut", on parle de constellations de nombres premiers ! (487, 491, 499, 503) est une constellation de motif 6-6-6. Pour parler de constellation, il ne faut pas que d'autres nombres premiers se glissent au milieu de la suite. Le principal but est de chercher à minimiser la différence entre le premier et le dernier terme de la suite.
Une autre conjecture sur les nombres premiers (la conjecture des constellations - ou première conjecture de Hardy-Littlewood) prétend que pour n'importe quel motif de constellation admissible (par exemple, (p,p+2,p+4) n'est pas admissible, car l'un de ces trois nombre sera divisible par 3), il existe une infinité de constellations. Cette conjecture est bien plus puissante que celle de Polignac !

S'il y a une première conjecture de Hardy-Littlewood, il y en a une deuxième !

Celle-ci dit que le nombre de nombres premiers en x et x+y est plus petit que le nombre de nombres premières inférieurs à y. En notant π(x) le nombre de nombres premiers inférieurs à x, cette seconde conjecture se résume par π(x+y)-π(x) ≤ π(y).

Et c'est là que le hic arrive : ces deux conjectures sont incompatibles ! Si l'une est vraie, l'autre ne le sera pas ! (A moins que les deux ne soient fausses...)

Le théorème de la progression arithmétique
Mais dans ces histoires, il n'y a pas que des conjectures, il ya a aussi des choses bien démontrées !
Par exemple, on sait qu'il existe un nombre infini de nombres premiers ! (C'est déjà pas mal, comme résultat, ça !...)

Et si on prenait une suite arithmétique ? Pour obtenir une suite arithmétique, on part d'un nombre donné, et on ajoute toujours le même nombre (appelé la raison). Par exemple, la suite des entiers impairs 1, 3, 5, 7, 9, ... est une suite arithmétique de premier terme 1 et de raison 2.
Depuis Legendre (fin du XVIIIe siècle), on sait que dans n'importe quelle suite arithmétique, il existe un nombre infini de nombre premiers ! (Enfin, seulement quand le premier terme de la suite et la raison son premier entre eux, c'est à dire, n'ont pas de diviseurs communs). Cela permet de dire par exemple que parmi les nombres impairs, il y a une infinité de nombres premiers (bon, en fait, excepté 2, TOUS les nombres premiers sont impairs...)
Autre exemple : premier terme 5, raison 7 : 5, 12, 19, 26, 33, 40, 47, 54, 61, 68,  75, ... Cette suite contient une infinité de nombres premiers ! A ce propos, suivant le premier terme de la suite choisi, on aura soit 0 ou 1 nombre premier (si le premier terme et la raison ont un diviseur commun), soit une infinité de nombre premier. Ce qui reste étonnant, c'est que dans ce deuxième cas, il y aura a peu près la même proportion de nombres premiers dans chaque sous-suite !
Petit exemple pour comprendre, avec la raison 6. Il y a une infinité de premiers lorsque le premier terme est 1 ou 5, et la proportion de premiers est à peu près la même dans ces deux suites :
0 -  6 - 12 - 18 - 24 - 30 - 36 - 42 - 48 - 54 - 60 - 66 - 72
1 -  7 - 13 - 19 - 25 - 31 - 37 - 43 - 49 - 55 - 61 - 67 - 73 -> 61%
2 -  8 - 14 - 20 - 26 - 32 - 38 - 44 - 50 - 56 - 62 - 68 - 74
3 -  9 - 15 - 21 - 27 - 33 - 39 - 45 - 51 - 57 - 63 - 69 - 75
4 - 10 - 16 - 22 - 28 - 34 - 40 - 46 - 52 - 58 - 64 - 70 - 76
5 - 11 - 17 - 23 - 29 - 35 - 41 - 47 - 53 - 59 - 65  - 71 - 77 -> 69%

En fait, ce résultat à propos de la proportion des nombres premiers pertmet de se dire que les nombres premiers ne sont pas si mal rangés que ça !

Le théorème de Green-Tao
Tout ça pour en arriver au théorème de Green-Tao, qui date de 2004, et qui a valu à Tao la médaille Field (le prix Nobel des maths) en 2006.

(5,11,17,23,29) est une suite arithmétique (de raison 6) de longueur 5 composée seulement de nombres premiers.
Mais peut-on trouver une telle suite, disons, de longueur 6 ?... Oui !
On a par exemple (7,37,67,97,127,157), de raison 30 et de longueur 6 !
Et si on se fixe pour longueur 25 ?

Bien sûr, on met un peut plus de temps dans la recherche, mais avec du courage, on trouve que la suite (6171054912832631 + 81737658082080 × n | 0≤n≤24) (Plus longue suite arithmétique de nombres premiers connue, trouvée en 2008)

Ce que Green et Tao ont démontré, c'est que pour n'importe quelle longueur fixée, il est possible de trouver une suite arithmétique de nombres premiers de cette longueur. Le moins de l'histoire, c'est qu'il ne dit pas comment la trouver !

---

Sources :
Du wikipédia et du mathworld, mais aussi :
Recherche de constellations de nombres premiers
Records de progressions arithmétiques

18 mai 2008

Le sac froid de Goldbach

(Ne cherchez pas trop de sens à ce titre)
Restons dans les nombres premiers, et aujourd'hui, résolvons une bonne fois pour toutes la conjecture de Goldbach ! Ce problème date de 1742, et attends toujours d'être résolu. Son énoncé de base était :

Tout entier supérieur à 5 est la somme de trois nombres premiers

C'est ainsi que Christian Goldbach a énoncé la conjecture dans une lettre adressée à Euler. Ce dernier, intéressé par le problème, en a donné une reformulation :

Tout entier pair supérieur à 2 est la somme de deux nombres premiers

(Ou, d'une façon équivalente, "tout entier supérieur à 2 est la moyenne de deux nombres premiers")
Et cela fait aujourd'hui 266 ans que des mathématiciens de tous pays cherchent à démontrer cet énoncé !
On peut déjà commencer par vérifier la validité de la conjecture sur les premiers nombres pairs :

4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7
12 = 5 + 7
14 = 3 + 11
16 = 3 + 13
18 = 5 + 13
20 = 3 + 17
22 = 3 + 19
...
1050 = 11 + 1039
1052 = 3 + 1049
...

Aux dernières nouvelles (février 2008), la conjecture a été vérifiée par l'informatique jusqu'à n=1.1×10¹⁸.

En fait, on a de très nombreuses raisons de penser que cette conjecture est vraie, à partir d'arguments probabilistes : plus le nombre est grand, plus il y a de façon de le décomposer en la somme de deux nombres (impairs), donc plus il y a de chance que ces deux nombres soient premiers tous les deux.
La théorie des nombres premiers nous apprend qu'un nombre m pris au hasard a une probabilité de 1/ln(m) (Une chance sur ln(m)) d'être premier.
Pour un entier pair n, et un entier m entre 3 et n/2, on a alors la décomposition n = m + (n-m). La probabilité que m et n-m soient à la fois premier est . Pour un n pair donné, on a n/2-2 choix de m possibles. Parmi tous ces choix de m possibles, il doit bien en avoir un qui fonctionne, peut-être même plus d'ailleurs. En fait, on peut s'attendre à ce que le nombre moyen de décomposition en deux nombres premiers de n soit P(n,3)+P(n,4)+...+P(n,n/2) = (qui tend vers +∞ lorsque n tend vers +∞)

Plus concrètement, cela veut dire que plus n est grand, plus l'on doit s'attendre à ce qu'un grand nombre de décompositions en deux nombres premiers existent. Et donc, plus n est grand, moins il faut espérer trouver de contre-exemple à la conjecture de Goldbach... Quand on sait qu'elle a été vérifiée jusqu'à n=1.1×10¹⁸...

Ce diagramme montre pour tous les nombres pairs entre 2 et 1 000 000 le nombre de décompositions possibles en somme de deux nombres premiers... Il y a toujours au moins 2000 décompositions pour les nombres plus grands que 500 000, on a du mal à concevoir qu'il puisse subitement en avoir un en dessous, encore moins à 0.

Autre fait intéressant : pour tous les nombres plus petit que 1 000 000, le plus petit des nombres de la décomposition ne dépasse jamais 5569 (dans la décomposition 389965026819938 = 5569 + 389965026814369)

Bon, en fait, ce raisonnement n'a rien d'une démonstration ! Déjà, la probabilité que m et n-m soient tous les deux premiers en même temps n'est pas juste, puisque le fait que l'un soit premier peut influencer l'autre. Et surtout, ce n'est qu'une histoire de probabilité, même si les probabilités sont plus qu'infimes, elles ne sont pas encore nulles.

Malgré tout ça, il y a certaines choses dont on est sûr.
D'après les travaux de Vinogradov, on sait que tout nombre pair est la somme de au plus 4 nombres premiers (On s'approche de 2...). On sait aussi que presque tous les nombres pairs peuvent s'écrire comme la somme de 2 nombres premiers (Malgré ses apparences, "presque tous" est une notion mathématique - cela signifie que la proportion des nombres qui ne vérifier pas la conjecture de Goldbach tend vers 0 - reste à montrer qu'elle est tout le temps égale à 0). Un autre résultat montre que tout nombre pair suffisament grand est la somme de deux nombres premiers et d'exactement 13 puissances de 2 !

Des variantes de ce problème existent :
- Ceux qui trouvent cette conjecture trop difficile peuvent s'attaquer à la conjecture faible de Goldbach : tout nombre impair supérieur à 7 est la somme de trois nombres premiers impairs. (Toujours à l'état de conjecture, mais les recherches avancent plus rapidement sur la conjecture faible que sur la forte)
- Ceux qui trouvent par contre cette conjecture trop facile à démontrer peuvent s'attaquer à la conjecture de Dubner : tout nombre pair supérieur à 4208 est la somme de deux nombres premiers p-jumeaux. (Un nombre premier n est dit "p-jumeau" s'il a un jumeau, càd, si n+2 est premier ou n-2 est premier - A ce jour, on ne sait pas s'il existe une infinité de nombres premiers jumeaux, et cette conjecture est jugée aussi difficile que la conjecture de Goldbach)
- Ceux qui trouvent ça encore trop facile peuvent s'attaquer à une conjecture dérivée de celle de Dubner : tout nombre pair suffisament grand est la somme de deux nombres premier min-jumeaux (Un nombre premier n  est "min-jumeau" si n+2 est premier).

Résoudre la conjecture de Dubner permettrait à la fois de démontrer la conjecture de Goldbach est la conjecture sur l'infinité des nombres premiers jumeaux, et ça, ça serait beau !
Reste plus qu'à le démontrer.
Pour avoir la moyenne, il vous faudra au moins démontrer la conjecture de Goldbach.
Pour espérer avoir une bonne note, il vous faudra résoudre celle de Dubner.
Vous avez 3 heures.

---

Sources :
Wikipédia (et toutes les sources en bas de page de wikipédia)
Wims, pour tester en ligne la conjecture de Goldbach

03 mai 2008

Une histoire de partie imaginaire

La spirale d'Ulam ou la spirale de Sacks, en plus d'un certain sens esthétique, donne quelques informations sur la distribution des nombres premiers. L'étude de ces nombres est importante pour élargir l'ensemble des connaissance mathématiques, mais importante aussi dans la sécurité bancaire.

L'hypothèse de Riemann est aussi un problème en relation avec la distribution des nombres premiers, donc avec la cryptographie, les transactions bancaires, les grandes entreprises et la bombe atomique.
Ce problème (insurmontable ?) récompensera d'un millions de dollars (par la Clay Mathematical Institute) quiconque parviendra à le démontrer !

Aujourd'hui, nous n'allons pas résoudre le problème, mais on va quand même essayer de le comprendre ! (le minimum requis est de connaitre les nombres complexes)

L'énoncé à démontrer est le suivant : "Les zéros non triviaux de la fonction zêta de Riemann ont tous pour partie réelle 1/2".
Il est vrai que dit comme ça, ça ne nous avance pas vraiment, tâchons d'y voir plus clair.

La fonction zêta de Riemann
La fonction zêta de Riemann (ou d'Euler) est une série (une somme infinie) qui ressemble à ça :

Pour s réel, cette série n'a de véritable sens que lorsque s>1.
Par exemple, on a :
(On retrouve la série harmonique pour s>1)
(Cette formule est la solution du problème de Bâle, loin d'être évident à montrer)

En fait, cette série a un sens pour s réel plus grand que 1, mais également lorsque s est un nombre complexe (de partie réelle >1). Il faut d'abord passer par la définition de la puissance d'un nombre complexe, mais c'est faisable !

Par une opération qui n'a pas lieu d'être expliqué sur ce blog (un prolongement analytique), on arrive à étendre la définition de notre fonction à tous les nombres complexes (sauf 1).

Représenter cette fonction sous forme de graphique n'est pas évident, puisqu'il s'agit d'une fonction complexe (deux dimensions) à valeurs complexes (2 dimensions) ; il nous faudrait 4 dimensions pour le représenter au mieux. On peut cependant représenter le module de ζ(s) en fonction de x+iy :

Plus c'est bleu, on on est proche de zéro... Où sont les zones bleues ?

Cette représentation permet de mettre en évidence le point 1, où la fonction tend vers l'infini (un pôle), ainsi que les points -2, -4, ½+i.14,13i et ½-i.14,13, où la fonction semble être égale à 0.
-2 et -4 sont des zéros triviaux : on montre que si s est un entier pair négatif, alors ζ(s)=0
et sont des zéros non triviaux. C'est de ces zéros que parle l'hypothèse de Riemann.

 

L'hypothèse de Riemann
La fonction zêta de Riemann est ce que l'on appelle une fonction "méromorphe", c'est à dire, une fonction à valeur complexe que l'on peut rapprocher d'une fonction rationnelle (un polynôme divisé par un autre). Pour de telles fonctions, connaitre les pôles (les points où la fonction tend vers l'infini) et ses zéros permet de connaitre entièrement la fonction (De la même façon que les racines d'un polynôme permet de le connaitre). Ceci explique pourquoi un tel intérêt pour les zéros de la fonction.

On connait bien une partie de ces zéros, les entiers pairs négatifs, appelés zéros triviaux :
ζ(-2)=ζ(-4)=ζ(-2n)=0 (n entier)
La fonction semble cependant s'annuler en d'autres points, et on suppose que ces points ont une partie réelle à ½. La question de l'hypothèse est là : montrer que tous les points où s'annule la fonction zêta ont une partie réelle égale à ½.
C'est à dire, si ζ(x+iy)=0, alors x=1/2 (ou x=-2n et y=0)

Ce que l'on sait, pour l'instant, c'est qu'il y a une infinité de zéros non triviaux, et que leur partie réelle est entre 0 et 1. On sait quand même que au moins un tiers des zéros non triviaux ont bien la partie réelle égale à 1/2.
Expérimentalement, il a été vérifié que l'hypothèse est vraie (aux erreurs de calcul près, un ordinateur ne peut représenter les nombres réels de manière exacte) pour les 1 500 000 000 premiers zéros non triviaux. Mais ça ne le justifie pas pour tous !

 

Bien que cette hypothèse ne soit toujours pas démontrée, beaucoup de théorème en sont une conséquence. En déduire un théorème que l'on sait faux serait une bonne façon d'infirmer l'hypothèse de Riemann, mais en attendant, tous ces théorèmes ne sont pas à 100% valides. (ce qui à un côté "dangereux", quand un théorème s'appuie sur un autre qui s'appuie sur un autre qui s'appuie sur l'hypothèse de Riemann...)

Et les nombres premiers, dans tout ça ?
J'y arrive ! C'est vrai que jusqu'à ici, on a vu apparaitre aucun nombre premiers, mais c'est Leonhard Euler qui découvre le rapport, grâce à l'égalité suivante :

Cette égalité permet de donner de bonnes indications sur la répartitions des nombres premiers ; ce n'est qu'une des conséquence de l'hypothèse de Riemann, parmi de nombreuses autres.

La fonction zêta est aussi la source d'un grand nombre d'autres problèmes. C'est bien d'avoir les zéros, mais combien valent t-ils ? Y a t'il des valeurs imaginaires rationnelles ? Et tout une ribambelle de questions sans réponses aujourd'hui !

---

Sources :
Wikipédia - d'où provient l'illustration (Et de nombreux endroits ailleurs)

28 juillet 2007

L'éternité, c'est long

Surtout vers la fin... [Woody Allen]

Mais c'est pourtant aujourd'hui que sort le jeu "Eternity II" dont je vais me faire un plaisir d'un faire la publicité pendant tout un article !
Eternity II, c'est ça (Une soixantaine d'euros dans tous les bons magasins de jouets) :

Il s'agit en fait d'un simple puzzle de 256 pièces, et en le terminant, on peut gagner la modique somme de 2000000 de dollars.
Deux millions de dollars pour un simple puzzle de 256 pièces, il doit surement y avoir une arnaque quelque part... Et vous n'avez pas tord de le penser !

En fait, les 256 pièces sont toutes carrées, avec un demis-motifs sur chaque côtés. Le but du jeu est de reconstituer le carré 16×16 avec les petites pièces, de manière à ce que chaque pièce corresponde avec sa voisine. Ma description n'est pas claire, le plus simple étant de tester la version en ligne, avec 16 pièces.

Le plus amusant la dedans est que l'on ne peut savoir si l'assemblage est bon seulement avant d'avoir posé la dernière pièce, comme on peut le voir sur cette image :

Mais revenons en au véritable jeu, à 256 pièces. Tout est là pour nous aider : on a déjà la position de l'une des pièces dessinée sur le plateau, on sait quels sont les 4 coins ainsi que les pièces du bord. On sait même qu'il y a 20 000 solutions différentes !

Bon, imaginons que l'on place toutes les pièces totalement au hasard : 256 pièces avec 4 angles différents possibles, ça donne 256!×4^256 façon de les placer, soit approximativement... 1,1×10^561 façons de les arranger...
Dans mon calcul, j'ai pas tenu compte des coins et de la pièce déjà placée, mais si je le fait, je trouve 4!×56!×195!×4^195 façons de les placer au hasard astucieusement.
Ce calcul donne
111531198469622492899759608971914595420947197274350519487727469101946513455
069377676358191758547254409098250127814533366537520303714516904568624054580
457715452150218419881603342689862313004029178711324849404505256052275017987
734577907767291619938991043571658075515174233907285048188722138784099296270
534509243817733468845560076206020218546046771585537232438151046330793578226
302780416097998170704433957446872507749953327176975289802388296970098802251
975215311015541008230129409675866681048622432256000000000000000000000000000
000000000000000000000000000000000
façons de placer nos 256 pièces (1,11×10^557). (Enfin, il y en a encore moins si on considère les pièces symétriques)
Même quand on sait qu'il y a 20 000 possibilités de réponses différentes, cela laisse une chance sur 10^552 d'avoir une bonne réponse en les plaçant de manière totalement aléatoire (à côté, l'Asaṃkhyeya est minuscule, et je ne parle pas des probabilités de gagner au loto, totalement ridicules)

Et pourquoi ne pas utiliser un ordinateur, alors ? Plusieurs solutions s'offriraient à nous :
* Essayer toutes les 10^552 solutions différentes, et regarder si elles fonctionnent. J'ai du oublier de préciser que le jeu est limité dans le temps, il faut trouver la solution avant le 31 décembre 2008 pour espérer gagner le 2 millions de dollars. Dépasser de très loin l'âge de l'Univers pour répondre à la question est tout à fait déconseillé...
* Programmer un logiciel permettant de résoudre la question le plus rapidement possible en prenant le problème dans sa globabilité, et donc, en utilisant la mathématique des nombres complexes, l'analyse combinatoire, la théorie des probabilités, mais aussi et surtout la théorie des pavages dits quasi périodiques, qui n'a qu'une trentaine d'années d'existence...

En fait, dans les deux cas, ça ne sert à rien de l'envisager, c'est pas possible, on a pas assez de temps... Le plus simple, finalement, c'est de prendre son temps et le faire à la main...
...

Et pendant ce temps là, l'institut allemand Fraunhofer IPK tente de reconstruitre le plus grand puzzle du monde, avec 600 millions de pièces, en numérisant toutes les pièces à l'aide de scanner à haute résolution et de bons ordinateurs. Le projet, c'est Stasi Puzzle project. Tout ça pour reconstituer les archives de la STASI de l'ex-RDA, que les agents de cette police secrète ont détruit au dernier moment après la chute du mur de Berlin. 16,5 km d'informations sur la population est-allemande sont à reconstruire pour que les familles puissent accéder à leur dossier. 600 millions de pièces, ce sont des fragments de page A4 déchirées à la main en 8, 12 voire 20 ou 40 morceaux. Ce projet devrait mettre normalement 5 ans à se boucler.
...

En attendant, le grand public a Eternity II pour gagner deux millions de dollars, ou au moins, passer le temps et s'amuser avec un vrai challenge !...

---

Sources :
Site officiel de Eternity II
L'article du Monde sur le sujet
Archives de la Stasi - Sciences & Vie n°1060, janvier 2006

14 juillet 2007

La formule de Marcel Pagnol

Marcel Pagnol : 28 février 1895 - 18 avril 1974. Écrivain, dramaturge, cinéaste et académicien français, on lui doit entre autre ses souvenirs d'enfance... Mais pas seulement ça ! On lui doit aussi ceci :

Si n est impair, alors n+(n+1)+n(n+1) est premier.

Pour n=1, 1+2+1×2=5 (premier)
Pour n=3, 3+4+3×4=19 (premier)
Pour n=5, 5+6+5×6=41 (premier)
etc.
Bon, évidemment, si il avait essayé n=11, il aurait vu que 11+12+11×12=155, qui n'est pas un nombre premier (Divisible par 5).

Un formule qui donnerait tous les nombres premiers, ça serait quelque chose de beau, non ?! Ca pourrait permettre d'avoir des nombres premiers aussi grands que l'on veut. Aujourd'hui, on ne connait pas de nombres premiers plus grands que 2^32582657+1...

Après tout, il y a bien une formule qui donne tous les nombres impairs (2n+1) ou une qui donne tous les nombres de Fibonacci (), alors pourquoi pas une formule qui donnerait tous les nombres premiers ?

Pagnol n'est pas le premier à s'y être cassé les dents avec sa formule (4n²+10n+5), Euler a été le premier à s'y atteler. A l'époque, il a trouvé la formule n² − n + 41... (Qui, évidemment, ne marche pas pour n=41, car le résultat sera divisible par 41). On a fini par démontrer qu'on ne pouvait pas trouver de polynôme a une seule variable donnant tous les nombres premiers.

Si cette formule existait, ça se saurait : on l'aurait depuis longtemps utilisé pour battre ce misérable record du nombre premier le plus grand (9 808 358 chiffres).

Et pourtant ! Il y a bien un polynôme qui donne la totalité des nombres premiers. On doit cette formule à Jones, Sato, Wada et Wiens en 1976. Voici la formule :

C'est vrai, on a déjà vu des formules plus simples, mais celle-ci fonctionne, elle peut donner tous les nombres premiers, pourvu que le résultat est positif. C'est simplement un polynôme de degré 25 avec 26 variables.

Evidemment, il y a un hic, quand on regarde de plus près la formule. Il s'agit du produit de deux membres : d'un côté, (k+2), et de l'autre, (1-plein de choses). Pour obtenir un résultat positif, il faut nécéssairement que le "plein de chose" soit nul : il s'agit finalement d'un système de 14 équations diophantiennes (à coefficients entiers) à 26 inconnues. Autant le dire simplement : c'est quasiment impossible d'avoir de solutions avec cette formule. A l'heure d'aujourd'hui, on a juste réussit à obtenir 2...

Mais ce n'est pas grave ! Lâchons les polynomes (même s'il y en a d'autres du même genre, dont un avec 10 variables, de de degré 1045) et cherchons une autre formule qui pourrait donner tous les nombres premiers.

Grace au théorème de Wilson (une histoire de congruence sur les nombres premiers), on a pu trouver une très chouette formule, qui donne tous les nombres premiers dans l'ordre :

(Les drôles de traits verticaux, c'est la fonction partie entière)

Sinon, si vous n'aimez pas les sinus et les factoriels, il y a aussi cette charmante formule plutôt basée sur les parties entières...

En fait, ces deux formules sont aussi inutilisables que la formule de Jones, Sato, Wada et Wiens, on a plus vite fait de prendre des nombres au hasard et de tester leur primalité par des algorithmes simples.

Tous ça pour dire que l'on cherche encore la formule miracle...
Si elle existe...

---

Sources :
Fortement inspiré de wikipédia
(Et un peu d'une conférence donnée à la fac sur le sujet)

08 juillet 2007

C'est l'facteur !

« La percée mathématique évidente serait le développement d'un moyen simple de factoriser les grands nombres en facteurs premiers. » [Bill Gates]

Non, je ne donnerai pas la clé du code de mon dernier article, vous n'avez qu'à trouver seuls la factorisation de 284191[...]27. Peut-être pas aujourd'hui, parce que nos ordinateurs en sont parfaitement incapables, mais peut-être que dans quelques années, si la puissance de nos ordinateurs évoluent et que les mathématiciens font bien leur boulot, la factorisation d'un nombre énorme sera quelque chose de faisable...

Mais au fait, pourquoi sommes nous aujourd'hui incapables de factoriser le n de mon précédent article ? Si tout va bien, je devrais y répondre au cours de cette note...

Digressons un peu : petite FAQ sur les nombres premiers ?

Qu'est ce qu'un nombre premier ?
Officiellement, c'est un nombre qui a exactement deux diviseurs : 1 et lui-même. Le genre de nombre impossible à diviser sous peine de se retrouver avec un nombre à virgule.
Qui donc a inventé ces nombres ?
Il s'agit apparemment de Grümf, le même qui a inventé la roue, il y a 23 000 ans...
Laurence Boccolini m'a dit que 1 était le premier nombre premier. C'est vrai ou pas ?
C'est faux, arrête de regarder TF1, ça ne te réussis pas. 1 n'est pas premier, il suffit de relire la définition : c'est un nombre qui a exactement deux diviseurs. Le nombre 1 ne possède qu'un seul diviseur, je vous laisse deviner lequel.
Et pourquoi on met le nombre 1 à l'écart comme ça ?
Parce que c'est bien plus pratique comme ça. Un théorème (appelé aussi théorème fondamental de l'arithmétique, ça serait dommage de l'infirmer) nous dit que tous les entiers naturels possèdent une décomposition unique en un produit de facteurs premier (aux permutations près). Par exemple, on a 12=2×2×3. Si 1 était un nombre premier, on aurait également 12=1×1×2×2×3, et la décomposition ne serait plus unique. Ca lui apprendra à être l'élément neutre de la multiplication !
Y'en a combien, des nombres premiers ?
Il y en a autant qu'on veut. Une infinité, quoi... Vous imaginez ce qu'il se passerait s'il y en avait un nombre fini ? Il suffirait de multiplier ensemble tous ces nombre premiers et d'y ajouter 1 pour se retrouver avec un nouveau nombre premier, ce qui serait embêtant...
C'est lequel le plus grand ?
Je viens de dire qu'il y en avait une infinité... Cependant, le plus grand que l'on ait calculé est un nombre de Mersenne, c'est à dire, de la forme 2ⁿ+1, avec n=32 582 657. Ca donne un nombre composé de 9 808 358 chiffres.

Maintenant cette petite mise au point faite, interressons-nous à cette histoire de factorisation. La force de l'algorithme RSA, c'est qu'il s'appuie sur la difficulté de décomposer un nombre composé en produit de nombre premiers, d'autant plus que les facteurs premiers sont de taille conséquentes.

Pour décomposer un nombre, la technique la plus simple est de tester un à un tous les nombres premiers pour voir s'ils divisent notre nombre.
Prenons 140.
2 est un diviseur de 140. On le garde de côté, il reste 70.
2 est encore un diviseur de 70. On le garde de côté, il nous reste 35.
2 n'est pas diviseur de 35, on passe donc au nombre premier suivant, c'est à dire 3.
En procédant ainsi, on trouvera facilement que 140=2×2×5×7.

Maintenant, si on s'amuse à chercher de la même façon pour décomposer 6887, on passera beaucoup plus de temps, puisqu'il faudra tester tous les nombres premiers uns à uns jusqu'à 71 avant de trouver que 6887=71×97.

Quand notre nombre à factoriser possède 309 chiffres, comme dans une clé de cryptage RSA classique, on ne peut pas décemment envisager le fait de tester tous les nombres premiers (ne serait-ce parce qu'il y en a au moins 10³⁰⁵).

Evidement, les algorithmes que l'on utilise en réalité sont plus efficaces que celui-ci, mais aucun d'eux n'arrive à donner des décompositions de gros nombres dans des temps raisonnables. En effet, les temps de calculs ne sont pas proportionnels à la longueur des nombres, mais à leur exponentielle. Ces algorithmes peuvent être rapides quand les nombres sont le produit de nombreux petits nombres premiers, mais dans le cas où l'on cherche à factoriser de grands nombres semi-premiers (un nombre produit de deux nombres premiers), l'attente serait vraiment trop longue.

L'idéal serait de trouver un algorithme rapide permettant de décomposer un nombre. Peut-être pas avec un temps de calcul proportionnel à la taille du nombre, mais au moins proportionnel à son carré, son cube ou autre... Un algorithme polynomial, en fait. Peut-être il existe, mais repose sur une propriété que l'on ne connait pas encore... Peut-être il n'existe pas, mais il faudrait le démontrer... Le mathématicien ou l'informaticien qui réussirait à répondre à cette question pourra finir ses jours heureux, vu l'argent en jeu...

En effet, le laboratoire RSA a lancé son propre concours : décomposez-moi ce nombre, et gagnez une somme conséquente en dollars. 200 000 $ sont prévus pour celui qui pourra donner les diviseurs premiers d'un nombre à 617 chiffres. Pour ceux qui visent moins haut, 30 000 $ sont prévus pour la factorisation d'un nombre à 211 chiffres. Ce challenge est plutôt réservé aux laboratoires qui prennent le temps de faire tourner leur ordinateur plusieurs mois durant, mais si vous vous ennuyez, vous pouvez toujours tester de multiplier des nombres au hasard. Mais c'est surtout un bon indicateur de la puissance des ordinateurs et des mathématiques.

Bref, tout ça pour dire qu'il faut faire attention à cette histoire de challenge RSA. Le jour où les 200 000 $ auront été gagnés, il faudra arrêter de se servir de sa carte bleue... Enfin, surtout pour Bill Gates, qui nargue tout le monde avec son argent protégé par des nombres à factoriser...

---

Sources :
Ben... Wikipedia !
Le challenge RSA

27 mai 2007

J'aimerais tant revoir Syracuse

"Prenez un entier supérieur à 1.
S'il est pair, divisez le par 2.
S'il est impair, multipliez-le par 3 et ajoutez 1.
Réitérez ensuite les deux précédentes étapes"

Ce qui est surprenant dans cette histoire, c'est que la suite obtenue tombera toujours sur 1, peut importe l'entier choisit au départ.

Et ce qui est encore plus surprenant, c'est que personne ne sait pourquoi !

Ce problème est couramment appelé Conjecture de Syracuse. (mais aussi problème de Syracuse, algorithme de Hasse, problème de Ulam, problème de Kakutani, conjecture de Collatz, conjecture du 3n+1 ou plus poétiquement la suite de grêlons)

On a encore beaucoup de mal à en décider la paternité, les tests ADN n'ont pas encore été faits...
En fait, tout commence avec Lothar Collatz, dans les années 1930, qui s'amuse à faire des transformations itératives d'entiers et regarde ce que ça donne.
Dans les années 50, Helmut Hasse se rend à l'Université de Syracuse (près de New York, pas du tout en Sicile) et remporte un grand succès en diffusant son problème.
Pendant la seconde guerre mondiale, le polonais Stanislas Ulam reprend le problème à son nom, et, dix ans plus tard, S. Kakutani reprend le problème pour le diffuser à son tour sous son nom.
Et, dans l'histoire, personne n'a réussit à le résoudre.
A l'époque de la guerre froide, on parlait de ce problème comme d'un complot soviétique pour ralentir les recherches aux États-Unis...
Dans ces années là, un mathématicien hongrois, Paul Erdõs, proposait 500$ à qui arriverait à résoudre le problème (ça vaut pas le millions offert à qui résolverait P=NP...).

Bref, toute cette fabuleuse histoire pour dire que le problème a déjà bien vécu, si bien qu'un joli vocabulaire s'est créé autour du problème.
La trajectoire (ou le vol) d'en entier donné est la suite donnée plus haut.
Le temps de vol, c'est le nombre de terme avant l'apparition du premier 1.
L'altitude maximale est simplement le plus grand terme de la suite.
Le temps de vol en altitude, c'est le nombre de termes nécessaires pour qu'un terme de la suite soit inférieur au premier terme (les plus matheux d'entre vous remarqueront qu'il suffit de démontrer que le temps de vol en altitude est fini pour démontrer la conjecture)
Le facteur d'expansion, c'est simplement l'altitude maximale divisée par le premier terme.

Et pour faire des choses jolies, on peut mettre ça sous forme graphique :

Avec tout ça, vous devriez pouvoir comprendre ce petit script :

 

Nombre de départ :

 

 

 

On peut s'amuser à chercher les nombres donnant le plus grand temps de vol, la plus grandes altitude maximale ou le plus long temps de vol en altitude inférieurs à un certain nombre.
Parmi les nombres inférieurs à 100, les champions sont 27 (en altitude maximale et temps de vol en altitude) et 97 (en durée de vol).
Parmi les nombres inférieurs à 1000, les champions sont 703 (en altitude maximale et temps de vol en altitude) et 871 (en durée de vol).
Vous pouvez ensuite tenter de chercher les meilleurs inférieurs à 10000...

En 2004, la conjecture a été vérifiée pour tous les nombres inférieurs à 2⁶⁴ (1,8 × 10¹⁹)
Les seules démonstrations que l'on a réussi a réussi à donner pour l'instant sont heuristiques (statistiques) : en considérant que les nombres impairs, on trouve qu'en moyenne, le prochain nombre impair vaut 3/4 du nombre précédent, ce qui a tendance à décroitre.
En 2006, Alain Slakmon et Luc Macot, mathématiciens québécois se basent la dessus pour donner une démonstration probabiliste de la question, démonstration vraie, mais, comme le signale leur auteurs, "Comme il s’agit d’une approche probabiliste, nous ne pouvons affirmer qu’il s’agit d’une preuve absolument irréfutable de la véracité de la conjecture. Il reste une toute petite possibilité que certains nombres y résistent". Cette possibilité est cependant petite... Mais pas impossible...

---

Sources :
Un site perso et un site moins perso
Article sur la démonstration probabiliste sur CyberSciences

05 mai 2007

Un millions de dollars pour un sudoku

(Je ne cherche pas à rentrer dans tous les rouages de la question, juste une visite guidée de détails plus ou moins intéressants)

Rappelez-vous, c'était il y a une semaine : vous avez découvert ce qu'était un problème NP-complet, comme celui de la faisabilité du sudoku (et plein d'autres, j'ai donné plein d'exemples), et ce qu'était un problème de classe P...

Le grand problème du problème NP-complet, c'est que dans l'état actuel des choses, un ordinateur met généralement beaucoup de temps pour en venir à bout. Savoir si un sudoku de 10 000 cases est faisable est pour un ordinateur quelque chose d'inenvisageable (avec le manque de chance, la réponse nécessiterait dans les 10^20000 calculs... )...

Inenviseageable ?... Là est la véritable question... Cette question porte un nom : "A t'on P=NP ?"
Peut-être il existe quelque part, bien caché, un algorithme capable de déterminer si ce sudoku est faisable en un temps admissible, polynomial...
Pendant ce temps là, les mathématiciens cherchent...

Et pour cause : un millions de dollars est prévu pour la personne qui arrivera à démontrer que P=NP, ou arrivera à démontrer son contraire.
Et pourtant, c'est facile de le démontrer : il suffit simplement de trouver un algorithme polynomial qui résolve un problème Np-complet (Ou alors montrer que pour un problème NP-complet précis, il est impossible de trouver un algorithme polynomiale qui réponde à la question).
Ce qui est bien avec les problèmes NP-complets, c'est qu'il sont tous plus ou moins pareils : en résoudre un, c'est la même chose que tous les résoudre. Montrer que un seul est polynomial, c'est montrer qu'ils le sont tous... Idem pour l'inverse.
Bon, c'est pas forcément évident, à vrai dire, mais c'est faisable, avis aux amateurs...
(Enfin, c'est en théorie à la portée des amateurs en cherchant une démonstration du type évoqué ci-dessus, mais tout porte à croire que si la démonstration existe, elle porterait plutôt sur les définitions précises des diverses classes)

Et en attendant d'avoir une démonstrations, qu'en pensent les mathématiciens ?... Un sondage (encore un...) a été réalisé en 2002 sur la question :
45 % pensent que la question sera résolue avant 2050
27 % pensent qu'elle sera résolue après
5% pensent qu'on ne trouvera jamais, que ça sert à rien de chercher et qu'il vaudrait mieux chercher autre chose
(Et les autres ne pensent rien sur la question)

Mais ce qui est encore plus intéressant, c'est la deuxième question posée dans le sondage : "Est-ce que P=NP ?". A ça, on a :
61% pensent que P≠NP
9% pensent que P=NP
Et les 30% qui restent... pensent que c'est ni l'un, ni l'autre...

Et si la véritable réponse était là... Et si la question P=NP était indémontrable ?...
C'est tout à fait possible, Gödel a démontré 1931 qu'en mathématiques, tout n'est pas démontrable. Un théorème indémontrable (dans un système de démonstration donné) est appelé "indécidable".
Heureusement, c'est possible de démontrer que quelque chose n'est pas démontrable (c'est ça qu'est beau, en mathématiques !)...

Et que se passe t'il si on montre que "P=NP ?" est indécidable ?... Et bien, on ne sera pas plus avancés : les ordinateurs rameront toujours autant pour trouver la réponse d'un problème compliqué, mais on pourra admettre que P≠NP, et démontrer de nouvelles choses à partir de ça...

Et pour résoudre le sudoku, on gardera le papier et le crayon. Ou alors, on peut lire un bon bouquin, les sudoku, en fait, c'est nul...

---

Sources :
Pour la science - n°334, août 2005

26 avril 2007

Norbert Petiot, voyageur de commerce

(En lisant entièrement cette note, vous pourrez peut-être gagner un millions de dollars)

Voyageur de commerce, quel beau métier ! Se balader de maisons en maisons et refourguer sa camelote... Mais comment peut on aujourd'hui songer à faire ce métier quand on sait qu'il va falloir passer son temps à marcher entre toutes les maisons...
"Et si, avec mes compétences d'informatiques, j'écrivais un algorithme qui me chercherait le moyen le plus court de relier toute les maisons ! Avec ça, je pourrai minimiser mon temps à marcher, et passer plus de temps à vendre ma camelote !". Après cette réflexion, Norbert Petiot se mit à programmer, il trouva se qu'il chercha : un algorithme qui trouve le plus court chemin entre n points. Il fait un petit test simple, avec 4 points. Le programme teste alors les 12 chemins possible et retourne en un centième de seconde le meilleur chemin.

Parfait, se dit-il, devant ce jeu d'essai. Il décide alors de rentrer ses données, les 15 maisons qu'il veut visiter et les 105 distances qui séparent chaque maison 2 à 2... Cette histoire a plus de 17 ans... On dit qu'il attend encore la réponse à son problème... (Plus que 96 jours à attendre, finalement)

Mais que s'est-il donc passé ? Pourquoi ce malheureux voyageurs de commerce est mort de faim devant son écran en se disant "plus que quelques secondes à attendre" ? A t-il mal réalisé son programme ?

Eh bien, il se trouve que Herbert s'est frotté à un problème NP-complet...

NP-complet ? Qu'est ce que c'est que cette bête là ?!
(Les histoires de théorie de la complexité étant plus compliquée qu'il n'y parait, il y aura un certain nombre de simplifications fort peu précises)
Pour résoudre un problème en informatique, on a tendance à utiliser des algorithmes. En théorie, on peut calculer n'importe quoi. En théorie seulement, puisque dans la pratique, on est toujours limités par la puissance des ordinateurs que l'on utilise. C'est pour cela que l'on peut catégoriser les différents problèmes par leur facilité à être résolus par des ordinateurs. Parmi ces différentes catégories, on parle surtout des classes P et des classes NP.

La classe P (polynomial)

"Voici une boîte d'allumettes avec n allumettes. Fonctionne t-elles toutes ?". Pour le savoir, il va falloir essayer toutes les allumettes en les allumant. Si elles fonctionne toutes, on pourra répondre oui à la question. Le temps dont on aura besoin pour le savoir sera donc proportionnel au nombre d'allumettes.

"Y a t'il un couple qui s'est formé pendant cette soirée comportant n personnes ?". Sachant que personne ne voudra vous répondre, il va donc falloir vérifier pour chaque couple s'il correspondent à l'idée qu'on se fait d'un couple. Le temps qui va falloir pour trouver la réponse sera donc proportionnel au nombre de couples que l'on peut former, et donc, proportionnel (à quelque chose près) à n².
On dit qu'on problème de décision (auquel on peut répondre oui ou non) est de classe P si on peut trouver un algorithme qui donnera une réponse certaine en un temps polynomial.

La classe NP (non-déterministe polynomial)

"Étant donné n villes, existe t'il un chemin passant par tous ces villes de longueur inférieure à N ?". Avec un peu de chance, on va pouvoir répondre oui très rapidement, sinon, le temps d'attente sera proportionnel à n!
Pour simplifier de manière atroce, les problèmes NP sont les problèmes dont le temps d'exécution, si on manque de chance, ne sera pas polynomial.
Et les problèmes NP-complet (ou NP-difficile en simplifiant) dans cette histoire ? Et bien, c'est l'ensemble des problèmes qui ressemblent à notre problème du voyageur de commerce (qui est NP-complet), c'est à dire, les problèmes dont l'algorithme de résolution ressemble (même de loin) à celui du problème du voyageur de commerce.

Quelques exemples de problèmes NP-complets :

Problème du circuit hamiltonien
"Étant donné un graphe, y existe t-il un cycle hamiltonien ?"
Alias, étant donné un graphe, existe t-il un chemin passant une et unique fois par tous les points ?

Peut-on trouver un cycle hamiltonien dans ce graphe ?... Réponse...

Problème de la séparation équitable
"Étant donné une suite d'entiers données, y a t-il moyen de la séparer en deux paquets de même somme ?"

Exemple : 1, 2, 2, 3, 3, 4, 5...
Réponse : Oui : 2+2+3+3=1+4+5

Problème du sudoku
"Ce sudoku n²×n² cases est-il faisable ?"

Exemple : ce sudoku est-il faisable ?... Réponse...

Problème des équations quadratiques diophantiennes
"L'équation ax²+by=c, avec a,b,c entiers donnés, admet-elle des solutions ?..."

Problème de Laurent Romejko
"Quel est le mot le plus long existant parmi ces n lettres" et "Avec des additions, soustractions, multiplications et divisions, peut-on obtenir une certaines sommes avec n chiffres donnés"...

Bref
Il existe énormément de problèmes NP-complet, et en résoudre un seul de manière déterministe (avec un algorithme polynomial) suffirait à empocher la somme de un millions de dollars...

Plus d'informations dans le prochaine article, parce cet article-là est déjà trop long.