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.
1. 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 […]
… pour nos abonnés, l'article se prolonge sur 2 pages…
