Introduction
La théorie de la complexité est le pilier théorique qui permet de comprendre et de classer la difficulté des problèmes informatiques. Elle ne se contente pas de savoir si un problème peut être résolu par un ordinateur (question de la calculabilité, traitée par la thèse de Church-Turing), mais cherche à savoir avec quelles ressources (temps de calcul, mémoire) il peut l'être de manière efficace. Cette distinction entre 'possible' et 'pratiquement faisable' est cruciale pour toute l'industrie informatique et a des implications profondes en cryptographie, en optimisation et en intelligence artificielle.
Description
La théorie de la complexité organise les problèmes en classes de complexité, définies par la quantité de ressources nécessaires à leur résolution par une machine de Turing déterministe ou non déterministe. Les classes fondamentales sont P et NP. La classe P (Polynomial time) contient les problèmes pour lesquels une solution peut être *trouvée* par un algorithme déterministe en un temps polynomial par rapport à la taille des données d'entrée (ex. : tri d'une liste, recherche du plus court chemin). La classe NP (Non-deterministic Polynomial time) contient les problèmes pour lesquels une solution *proposée* peut être *vérifiée* en temps polynomial, même si la trouver peut être extrêmement long (ex. : le problème du voyageur de commerce, la satisfiabilité d'une formule logique). Le célèbre problème 'P = NP ?' demande si ces deux classes sont identiques, c'est-à-dire si tout problème dont la solution est facile à vérifier est aussi facile à trouver. D'autres classes importantes incluent EXPTIME (temps exponentiel), PSPACE (problèmes nécessitant une quantité polynomiale de mémoire) et la classe des problèmes NP-complets, les problèmes les plus difficiles de NP, dont la résolution efficace entraînerait P = NP.
Histoire
Les fondements de la théorie de la complexité ont été posés dans les années 1960 et 1970. Les travaux de Juris Hartmanis et Richard E. Stearns sur la hiérarchie en temps (1965) et ceux de Stephen Cook sur la NP-complétude (1971) sont des jalons majeurs. Cook a démontré que le problème de la satisfiabilité booléenne (SAT) est NP-complet, ouvrant la voie aux travaux de Richard Karp qui a identifié 21 problèmes NP-complets en 1972. Cette découverte a montré que de nombreux problèmes pratiques en optimisation, logistique et conception partageaient une difficulté fondamentale. Le problème 'P = NP ?' a été formulé explicitement par Cook et Leonid Levin et est devenu l'un des sept 'Problèmes du Prix du Millénaire' de l'Institut Clay en 2000, avec une récompense d'un million de dollars pour sa résolution.
Caracteristiques
1. **Approche asymptotique** : La complexité est analysée pour de grandes tailles d'entrée, en utilisant la notation grand O (O(n), O(n²), O(2^n)). 2. **Modèle de calcul** : Elle utilise généralement la machine de Turing comme modèle de référence, garantissant une robustesse indépendante de la technologie. 3. **Classes de complexité** : Structuration hiérarchique des problèmes (P, NP, co-NP, PSPACE, etc.). 4. **Réductions** : Technique clé pour comparer la difficulté des problèmes. Si un problème A peut être 'réduit' efficacement à un problème B, alors B est au moins aussi difficile que A. 5. **Distinction déterministe/non-déterministe** : La différence entre vérification et découverte est centrale. 6. **Analyse dans le pire des cas** : Elle évalue la performance garantie de l'algorithme le plus défavorable, par opposition à l'analyse en moyenne.
Importance
L'importance de la théorie de la complexité est immense. En cryptographie, la sécurité du chiffrement RSA repose sur l'hypothèse que la factorisation des grands nombres entiers (un problème de NP, mais pas supposé NP-complet) est difficile pour les ordinateurs classiques. En algorithmique, elle guide les développeurs vers des solutions approchées (algorithmes d'approximation) ou heuristiques pour les problèmes NP-difficiles. Elle pose des limites fondamentales à ce qui est calculable dans un temps raisonnable, influençant la conception matérielle, la biologie computationnelle (repliement des protéines) et l'apprentissage automatique. La question 'P = NP ?' est considérée comme l'une des plus profondes de l'informatique et des mathématiques, avec des implications qui révolutionneraient la science, l'économie et la technologie si elle était résolue positivement.
