Modèles de calcul et complexité
Cours de base (30 h de cours, 30h de TD)
Cours : Marianne Delorme (Marianne.Delorme)
TD : Pascal Koiran (Pascal.Koiran)
Comprendre et délimiter le champ du calcul algorithmique nécessite de définir formellement des notions de calcul et d'algorithme, ce que réalisent divers modéles de calcul.
Evaluer, en fonction de ressources ressortissant d'un modèle le coût d'un algorithme ou la décidabilité d'un problème exprime leur complexité. Une part de la théorie de la complexité est de classer les problèmes algorithmiquement résolubles en fonction des ressources nécessaires à leur résolution.
L'objet de ce cours est essentiellement l'étude des classes de complexité en temps et en espace définies via les machines de Turing, en particulier l'étude de leurs structures et de leurs relations. C'est aussi de situer des questions qui restent ouvertes dans ce champ et comment elles conduisent à considérer d'autres types de complexité.
- 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.
- 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. Relativisation et hiérarchie polynomiale.
- Problèmes algorithmiquement mais pas pratiquement résolubles. Théorèmes de hiérarchie.
- Complexité abstraite.
- Preuve interactive, un autre regard sur PSPACE.
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.