© Daniel Etzold - Fotolia
D
ossier
25
© DR
Bernard Chazelle
Department of Computer Science, Princeton University
Les deux dernières décennies ont vu l’émergence d’une
théorie de l’aléa algorithmique dont les conséquences
sur la notion de preuve ont une portée philosophique à
même de surprendre. Voici, en quelques mots, ce dont
il s’agit.
P, NP et tout cela
En informatique théorique, la complexité d’un problème désigne la quantité de ressources nécessaires
à sa solution. Il est d’usage de se limiter à trois types de ressources : le temps, l’espace et l’aléa. L’algo-
rithme scolaire pour la multiplication, par exemple, requiert un temps quadratique : en effet, multiplier
deux entiers de
n
chiffres nécessite un nombre d’opérations élémentaires de l’ordre de
n
2
. L’espace requis
est également quadratique, mais il est facile de le rendre proportionnel à
n
. Existe-t-il un algorithme plus
rapide ? Curieusement, en faisant un détour par la transformée de Fourier, on peut réduire le temps
d’exécution à une fonction proche de
n
log
n
. Cet algorithme est certes trop compliqué pour détrôner celui
enseigné à l’école primaire, mais sa rapidité justifie sa présence au cœur de certains codes cryptogra-
phiques.
Un problème est dit polynomial s’il peut être
résolu
en un nombre d’étapes proportionnel à
n
c
, où
n
dénote
la taille du problème et
c
est une constante. C’est notamment le cas de la multiplication, de la transfor-
mée de Fourier, de la programmation linéaire et de bien d’autres tâches d’usage courant. Ces problèmes
constituent la classe P, dont la contrepartie, la classe NP, regroupe les problèmes dont la solution peut être
vérifiée
en temps polynomial. Considérons le problème de factoriser un entier
N
de
n
chiffres. Il y a lieu
de croire (et d’espérer) que c’est un problème difficile, c’est-à-dire non résoluble en temps polynomial ;
en revanche, vérifier qu’une suite de nombres premiers factorise
N
est facile, puisque ce n’est qu’affaire
Les surprises de la complexité
algorithmique
