Course Introduction and Overview: Graduate Complexity Lecture 1 at CMU

Ce premier cours de complexité computationnelle de niveau graduate, donné par Ryan O’Donnell à Carnegie Mellon, présente une vue d’ensemble des thèmes qui seront abordés au semestre. Le professeur commence par distinguer la théorie des algorithmes, qui cherche des algorithmes efficaces, de la théorie de la complexité, qui cherche à prouver l’absence de tels algorithmes. Il souligne la difficulté de cette dernière, due à la nécessité de prouver des résultats négatifs et à l’existence d’algorithmes surprenants. Le cours se concentrera sur trois grands thèmes : la complexité en temps, la complexité de circuits et le rôle du hasard. Après avoir rappelé les définitions de base (langages, machines de Turing, classes de complexité), il présente le théorème de hiérarchie temporelle, qui montre que plus de temps permet de décider plus de langages, et en déduit que P est strictement inclus dans EXP. Il introduit ensuite les classes de complexité en espace, et les relations entre temps et espace, notamment le théorème de Hopcroft-Paul-Valiant qui montre que l’espace est plus puissant que le temps. Enfin, il introduit le nondéterminisme et la classe NP, et pose la question centrale P vs NP, qui reste ouverte. Le cours se termine sur l’annonce des prochains sujets : hiérarchie temporelle, complexité de circuits et dérandomisation.