Magistère d'Informatique, première année, Complexité

Le polycopié complet (sans les solutions des exercices)
Christos H. Papadimitriou: Computational Complexity, Addison Wesley, 1995, Reading MA.: C'est l'ouvrage principal utilisé pour ce cours. Il devrait être disponsible à la bibliothèque centrale de l'école.
John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979, Reading MA.: Utilisé pour quelques matérieux supplémentaires.
Neil Immerman: Nondeterministic Space is Closed Under Complementation, SIAM J. Comput. 17, No. 5 (Oct., 1988), 935-938.: Joli petit papier, le contenu est aussi dans le Papadimitriou
Michael Garey et David S.Johnson : Computers and Intractability. W. H. Freeman and Company, 1979.: S'intéresse principalement à la théorie de la NP-complétude. Bonne présentation pas trop formelle. Cet ouvrage est très apprécié parmi les chercheurs pour son catalogue de problèmes NP-complets qui est toujours très utile, malgré son âge de 25 ans.