Théorie de la complexité computationnelle
La théorie de la complexité computationnelle classe les problèmes en fonction de la quantité de temps, de mémoire et d'autres ressources nécessaires à tout algorithme pour les résoudre, traçant des frontières claires entre ce qui est résoluble efficacement et ce qui semble intraitable.
Definition
La théorie de la complexité computationnelle étudie la difficulté intrinsèque des problèmes computationnels mesurée par les ressources, principalement le temps d'exécution et la mémoire, nécessaires pour les résoudre sur un modèle tel que la machine de Turing, et regroupe les problèmes en classes de complexité en conséquence.
Scope
Ce domaine couvre les classes de complexité en temps et en espace telles que P, NP, PSPACE et la hiérarchie polynomiale, la théorie de la NP-complétude et des réductions polynomiales, la question centrale P versus NP, ainsi que les modèles à ressources bornées intégrant l'aléatoire, l'interaction et les preuves, de même que les résultats de hiérarchie et de dureté qui relient ces classes.
Sub-topics
Core questions
- Combien de temps et de mémoire la résolution d'un problème donné requiert-elle intrinsèquement ?
- Quels problèmes peuvent être résolus efficacement et lesquels semblent résister à tous les algorithmes efficaces ?
- Comment est-il démontré que des problèmes sont aussi difficiles que les membres les plus difficiles d'une classe de complexité ?
- L'aléatoire, l'interaction ou le non-déterminisme ajoutent-ils une réelle puissance de calcul ?
Key theories
- Théorèmes de hiérarchie en temps et en espace
- Avec strictement plus de temps ou d'espace, les machines peuvent résoudre strictement plus de problèmes, prouvant que les classes de complexité forment de véritables hiérarchies et que certains problèmes sont intrinsèquement plus difficiles que d'autres.
- NP-complétude
- Le théorème de Cook-Levin identifie des problèmes dans NP auxquels tout autre problème NP se réduit, de sorte qu'un seul algorithme efficace pour l'un d'entre eux permettrait de les résoudre tous efficacement.
- Modèles à ressources bornées
- L'ajout d'aléatoire, d'interaction ou d'alternance définit des classes telles que BPP, IP et la hiérarchie polynomiale, dont les relations affinent la compréhension de ce que des ressources supplémentaires peuvent ou ne peuvent pas apporter.
Clinical relevance
La théorie de la complexité guide la pratique en certifiant quels problèmes admettent des algorithmes efficaces et lesquels sont NP-difficiles (NP-hard) et sont donc mieux abordés par des heuristiques ou des méthodes d'approximation ; la difficulté présumée de certains problèmes sous-tend également la cryptographie moderne, dont la sécurité repose sur des tâches considérées comme computationnellement infaisables.
History
Hartmanis et Stearns ont fondé le domaine en 1965 en définissant les classes de complexité et en prouvant des théorèmes de hiérarchie. Cook et Levin ont introduit la NP-complétude vers 1971, Karp a montré que de nombreux problèmes naturels étaient complets en 1972, et les décennies suivantes ont vu l'ajout de modèles de preuve aléatoires, interactifs et vérifiables de manière probabiliste.
Key figures
- Stephen Cook
- Richard Karp
- Leonid Levin
- Juris Hartmanis
Related topics
Seminal works
- cook1971
- hartmanisStearns1965
- aroraBarak2009
Frequently asked questions
- Quelle est la différence entre la calculabilité et la complexité ?
- La calculabilité se demande si un problème peut être résolu par un algorithme quelconque, sans tenir compte du coût. La complexité suppose que le problème est résoluble et se demande quel doit être le coût de cette solution en temps et en mémoire, établissant des distinctions plus fines parmi les problèmes résolubles en principe.
- Pourquoi la NP-complétude est-elle importante en pratique ?
- Lorsqu'un problème est démontré NP-complet, il est lié à des milliers d'autres pour lesquels aucun algorithme efficace n'est connu malgré des décennies d'efforts. Cela indique que la recherche d'un algorithme exact rapide est probablement vaine et que l'approximation, les heuristiques ou les méthodes pour cas particuliers constituent la voie réaliste.