Complexité Turing
Cours de base (30 h de cours, 30h de TD)
Cours : Marianne Delorme (Marianne.Delorme)
TD : Pascal Koiran, Damien Regnault (Pascal.Koiran, Damien.Regnault)
Plan du cours.
-
Divers modèles de calcul caractérisant, via la thèse de Church-Turing, la classe des fonctions effectivement calculables. Exemples de modèles strictement moins et strictement plus puissants. Systèmes de programmation acceptables, isomorphisme de Rogers.
- Classes de complexité-Turing en temps et en espace, déterminées par une fonction. Comparaisons.
- Les classes P, NP (et Co-NP). Leurs structures : réduction polynomiale et réduction en espace logarithmique. Langages NP (P, Co-NP)-complets.
- La classe PSPACE. Langages PSPACE-complets. Relativisation (machines de Turing avec oracle) et hiérarchie polynomiale.
- Problèmes algorithmiquement mais pas pratiquement résolubles. Théorèmes de hiérarchie.
- Preuve interactive, une autre vision de PSPACE et une nouvelle technique de preuve : l'arithmétisation.
Bibliographie
-
H. R. Lewis and C. H. Papadimitriou, Elements of the theory of computation, Prentice Hall, 1981.
- C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
- Ding-Zhu Du and Ker-I Ko, Theory of computational complexity, Wiley and sons, 2000.
- L. A. Hemaspaandra and M. Ogihara, The complexity theory companion, Springer, 2002.