© Denis Junker - Fotolia
© Dreaming Andy - Fotolia
33
26
La Lettre
de multiplications : la factorisation est donc dans NP. Mais pourquoi espérer que ce soit une opération
difficile ? Parce que le sort de toute la cryptographie à clé publique, et donc du commerce électronique,
en dépend. En rendant la factorisation facile (autrement dit, polynomiale), les ordinateurs quantiques
promettent de bouleverser cet ordre. Encore faut-il qu’ils voient le jour...
Le paradoxe de l’aléa
Le choix du concept polynomial dans la définition de P provient de deux observations. D’une part, pour
des raisons pratiques, seuls les algorithmes polynomiaux sont viables pour les ordinateurs. D’autre part,
la classe P est invariante par l’opération de composition : il est ainsi possible d’assembler des algorithmes
pour en créer d’autres - un peu comme on assemble des Lego
®
- afin de réduire un problème à un autre.
À cette propriété se retrouve associé le concept de NP-complétude, qui désigne les problèmes les plus
difficiles dans NP - une classe extrêmement riche : automatiser la preuve des théorèmes mathématiques,
par exemple, est NP-complet, de même que résoudre un système d’équations quadratiques modulo 2,
simuler le repliement des protéines ou, encore, colorier un graphe en assignant des couleurs à ses som-
mets de façon à rendre toutes les arêtes bichromatiques. La classe des problèmes NP-complets jouit
d’une propriété remarquable : savoir résoudre n’importe lequel d’entre eux en temps polynomial permet-
trait d’en faire de même pour tous les autres. Cette universalité est à même de surprendre. Elle implique
qu’une solution rapide pour le coloriage de graphe, autrement dit P = NP, entraînerait automatiquement
une méthode rapide pour découvrir une démonstration de l’hypothèse de Riemann. Il n’est donc guère
surprenant qu’un consensus se soit formé autour de la conjecture P ≠ NP. Cette inégalité, sans aucun
doute l’un des plus grands défis scientifiques de notre époque, formalise l’intuition que trouver est plus
dur que vérifier, que la créativité ne peut être automatisée, que composer la
Messe en si mineur
est plus
ardu que d’apprécier le génie de cette musique.
