Jean-François Rey

Décidabilité, complexité et approximation

Alan Mathison Turing

Ce cours propose une introduction à la théorie de la complexité structurelle. Il comporte trois parties :

  • La première partie du cours explore la frontière entre les problèmes pour lesquels il existe une solution algorithmique et ceux qui n'en possèdent pas :
    1. Fonctions élémentaires, primitives récursives, récursives et modèles de machines.
    2. Thèse de Church. Nombres de Gödel. Théorème de la forme normale. Théorème s-m-n.
    3. Réduction de Karp. Exemples de problèmes indécidables.
  • La deuxième partie du cours montre comment classser les problèmes en fonction de leur complexité temporelle ou spatiale, c'est-à-dire en fonction du temps et de l'espace d'exécution nécessaire pour traiter ces problèmes algorithmiquement :
    1. Réductions et classes de complexité (P, NP, EXP, PSPACE...).
    2. Théorème de Cook-Levin, Théorèmes hiérarchiques, Théorème de Savitch, Théorème d'Immerman-Szelepscényi.
    3. Liens entre les complexités temporelles et les complexités spatiales.
  • Si le temps le permet, la dernière partie du cours présente les classes d'approximation, c'est-à-dire la classification des problèmes en fonction des propriétés des algorithmes qui leur fournissent une solution approchée raisonnablement fiable.

Ressources pour le cours :

Ressources pour les TD :

Ressources complémentaires :

Bibliographie :

  • J. L.Balcazar, J. Diaz, J. Gabano. Structural Complexity I. Springer-Verlag, 1988, EATCS Monographs on Theoretical Computer Science.
  • D. P. Bovet, P. Crescenzi. Introduction to the Theory of Complexity, Prentice Hall, 1994.
  • N. J. Cutland. Computability. Cambridge, University Press, 1980.
  • M. Davis, R. Sigal, E. J. Weyaker. Computability, Complexity and Languages. Academic Press, 1994, Fundamentals of Theoretical Computer Science.
  • Ding-Zhu Du, Ker-I Ko. Theory of Computational Complexity. Wiley, 2000.
  • M. R. Garey, D. S. Johnson. Computers and Intractability, A guide to the Theory of NP-Completeness. Freeman, 22nd ed. 2000.
  • D. S. Hochbaum. Approximation Algorithms for NP-hard problems. PWS Publishing Company, 1997.
  • J. E. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata theory, Languages and Computation (second edition). Addison Wesley, 2001.
  • C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1995.
  • J.-F. Rey. Calculabilité, complexité et approximation. Vuibert, 2004.
  • M. Sipser. Introduction to the Theory of Computation. PWS publishing Company, 1997.
  • V. V. Vazirani. Approximation Algorithms. Springer, 2001.