Le dossier sur « les problèmes difficiles en mathématiques » dans le journal « la Recherche » d’avril 2007 indique 7, pardon plus que 6 manières de devenir millionnaire en résolvant des problèmes de maths.
Pour commencer, l’article présente un intéressant « arbre de la complexité » des problèmes mathématiques qui ressemble à çà:
- problèmes ouverts (n’ayant pas encore de réponse)
- non formulé : n’ayant pas d’énoncé précis en termes mathématiques. Exemple : justifier les équations de Navier-Stokes (voir plus bas)
- conjectures : problèmes formulés non résolus.
- indécidables : problèmes dont on a démontré qu’ils sont indémontrables. Exemple : le second problème de Hilbert, qui propose de démontrer la cohérence de l’arithmétique, donc que ses axiomes ne sont pas contradictoire. Gödel a montré en 1931 que ce n’était pas possible sans sortir de l’arithmétique en ajoutant des axiomes.
- décidables : problèmes pour lesquels on sait qu’il existe une solution, positive ou négative
- preuve (négative) avec contre-exemple. Le troisième problème de Hilbert postule qu’étant donné deux polyèdres de même volume, il est toujours possible de découper l’un d’eux en polyèdres et de former l’autre en les réassemblant. Max Dehn montra qu’il est impossible de passer du tétraèdre au cube.
- Théorèmes:
- autres théorèmes (que ceux dits « d’existence », ci-dessous). Exemples : le Grand Théorème de Fermat, démontré par Wiles en 1993, et la Conjecture de Poincaré, qui vient d’être démontrée (voir plus bas)
- théorèmes d’existence, postulant l’existence d’un objet mathématique ayant certaines propriétés, objet qu’il suffit de trouver…
- démonstration par l’absurde : on démontre que la négation du théorème aboutit à une contradiction. Exemple : en 1761 J.H. Lambert prouva la transcendance de pi, puis celle de e^a, quel que soit a.
- méthode, ou « algorithme » : une séquence finie d’opérations permet d’obtenir une solution
- complexité inconnue : le problème du voyageur de commerce (un problème qui me poursuit…)
- non polynomiale : l'arithmétique de Presburger
- polynomiale
- grand degré : le test de primalité AKS permet de savoir avec certitude si un nombre de n chiffres est premier ou pas en n^12 opérations, ce qui peut être beaucoup plus court que d’effectuer les divisions
- petit degré : tous les algorithmes « classiques », par exemple le calcul du PGCD
de Hilbert à Clay
en 1900 David Hilbert présenta 23 problèmes très difficiles. 17 ont été résolus pendant le XXème siècle. En 2000, Landon Clay a offert 1 million de dollars pour la résolution de chacun des 7 problèmes du millénaire
- La Conjecture de Poincaré. Grigori Perelman a démontré cette conjecture en 2003. Après avoir refusé la médaille Fields en 2006, refusera-t-il aussi le million de dollars de la fondation Clay ?
- La Conjecture de Birch et Swinnerton-Dyer
- la Conjecture de Hodge
- l'Hypothèse de Riemann
- la Théorie de Yang-Mills qui a d’importantes conséquences en physique des particules
- une meilleure compréhension des équations de Navier Stokes qui décrivent les écoulements turbulents de fluides, mais paraissent trop compliquées pour décrire un phénomène physique si fondamental. C’est le type même d’énoncé difficile à formuler en termes mathématiques, c’est pourquoi la fondation Clay a du définir clairement certains aspects de ce problème pour pouvoir proposer le prix.
- le Problème P = NP, un problème fondamental en informatique théorique posé en 1970 : est-il possible de résoudre un problème de la classe « NP-complet » en temps polynomial, ou est-ce impossible ?
