Cours fondamental 1 (Com, Log)
La théorie de la complexité (II)
Timothy Gowers
Contact : timothy.gowers à college-de-france.fr
Pas de notes de cours prévues.
Langue du cours : Français
Présentation
L'objectif de ce cours est de présenter plusieurs classes de complexité informatique, des inclusions entre elles et des résultats sur la complétude. Bien que ce cours soit le deuxième d'une série sur la complexité informatique, il ne dépendra pas du premier cours de la série. En effet, il est plus proche d'un cours d'introduction que le cours de l'année dernière.
Contenu
- Introduction à plusieurs classes de complexité
- Relations simples entre les classes de complexité
- Relations moins évidentes entre les classes de complexité (I)
- Relations moins évidentes entre les classes de complexité (II)
- Problèmes complets pour certaines classes de complexité
- Formules, programmes branchés, et le théorème de Barrington
Prérequis
Aucun cours n'est nécessaire. Aucun cours n'est un prérequis. Une connaissance de la définition d'une machine de Turing serait utile, mais elle sera rappelée au début du cours.
Bibliographie