Bibliogr. p. 311-330

Premier ouvrage en langue français traitant de la complexité en tant que telle, Complexité et algorithmique avancée est conçu pour être abordé par les étudiants des trois cycles universitaires d'informatique et de cognitique.
On y trouvera une introduction aux concepts fondamentaux du domaine, qu'il s'agisse de machine de Turing élémentaire ou universelle, de complexité au sens de Levin-Cook ou de Kolmogorov. Y sont également définies les trois principales classes de complexité, P, NP et NPC, ainsi que le concept de quantité absolue d'information dû à Kolmogorov. Dans une dernière partie, on montre comment résoudre certains problèmes en faisant "tomber"" la complexité en utilisant des concepts probabilistes ou des méthodes d'énumération implicite dont les principes sont décrits.
l'ouvrage s'achève avec un chapitre consacré à l'informatique quantique.