COMPLEXITÉ, mathématique

Au cœur de l'informatique théorique, la théorie du calcul – ou théorie de la calculabilité – née dans la décennie 1930 des travaux de Kurt Gödel (1906-1978), Alan Turing (1912-1954) et Alonzo Church (1903-1995), répond à des questions sur ce qui est faisable dans l'absolu par le calcul avec un ordinateur. Elle énonce des résultats négatifs du type : il est impossible d'écrire un programme – aussi long et complexe soit-il – qui, chargé d'analyser d'autres programmes, repère ceux qui se perdent dans une boucle et ne se terminent jamais (indécidabilité de l'arrêt d'un programme). Ces preuves d'impossibilité sont importantes et une fine répartition entre ce qui est algorithmiquement faisable et ce qui ne l'est pas, est maintenant disponible.

Les classes P et NP

Ce domaine a ouvert la voie dans la décennie 1970 à une analyse d'un niveau plus fin, appelée théorie des classes de complexité, où l'on se pose des questions du type suivant : peut-on décomposer en facteurs premiers un nombre de n chiffres en utilisant un temps de calcul t majoré par un polynôme en n (on parle de temps polynomial) ? Les problèmes que l'on peut traiter en temps polynomial constituent la classe de complexité P. On considère qu'un problème dans la classe P non seulement est algorithmiquement traitable, mais qu'on peut le résoudre avec efficacité. Dans le cas contraire, on dit que le problème est intrinsèquement difficile. Bien sûr, connaître la classe de complexité P est important et de très nombreux travaux ont été menés dans ce but. En 2002 par exemple, des chercheurs indiens ont démontré un résultat attendu depuis deux décennies : le problème de savoir si un nombre est premier (problème de la primalité) est dans la classe P (le problème de la primalité n'est pas équivalent à celui de la décomposition en facteurs premiers, car on arrive parfois à savoir qu'un nombre n'est pas premier sans pour autant disposer d'aucun de ses facteurs non triviaux).

La question suivante a aussi été considérée : connaissant une éventuelle décomposition d'un nombre de n chiffres en facteurs non triviaux a et b, peut-on vérifier en temps polynomial qu'elle est correcte, c'est-à-dire que n = a.b ? La réponse ici est oui, car on sait effectuer la multiplication des deux nombres a et b en temps polynomial. Plus généralement, les problèmes dont on peut ainsi vérifier les solutions en temps polynomial constituent la classe NP. Le problème de la factorisation est dans la classe NP (d'après ce que nous venons de dire concernant la multiplication des entiers), en revanche on ignore si le problème de la factorisation est dans la classe P, et l'on pense généralement qu'il n'y est pas. C'est une question importante pour la cryptographie, où casser certains algorithmes cryptographiques est équivalent à factoriser des entiers.

Il semble intuitivement clair que la classe NP n'est pas identique à la classe P – car il est certainement plus facile de vérifier une solution proposée que de la rechercher ! Pourtant, la démonstration de l'affirmation P ≠ NP est l'une des énigmes les plus récalcitrantes de la théorie des classes de complexité. Un prix d'un million de dollars est offert pour qui prouvera ce résultat ou son opposé : P = NP. Il y a trente ans, on découvrait ce problème qu'on espérait résoudre rapidement ; en 2004, malgré de multiples tentatives – et le prix ! –, on cherche toujours en vain sa solution.

Cette situation de blocage est gênante, car elle se produit en un point central de la théorie de la complexité : tant que cette question ne sera pas proprement réglée, la théorie des classes de complexité sera entravée, et aucun des résultats dont on a besoin en cryptographie pour prouver de[...]