THX - Théorie de la complexité

Master 1 - ENS Rennes - Année 2018/2019

Cours + travaux dirigés : François Schwarzentruber
Page du projet wikipedia

lundi 17 septembre 2018	Introduction Problèmes de décision. Langage. Codage. Algorithme non-déterministe. Panorama des classes complexité. Tuiles de Wang. Problème de pavage d'un carré. SAT. Réductions polynomiales. Théorème de Cook. The convenience of tilings. Peter van Emde Boas PRIMES is in P. Agrawal, Kayal, Saxena (prix Fulkerson 2006)
lundi 24 septembre 2018	TD
lundi 1er octobre 2018	Complexité en espace Théorème de Savitch. PSPACE. Pavage d'un corridor. Formules booléennes quantifiées. Rendu DM1
lundi 8 octobre 2018	TD
lundi 15 octobre 2018	Complexité en espace logarithmique L et NL. Accessibilité dans un graphe orienté. Réduction en espace logarithmique. Théorème d'Immerman-Szelepcsényi (NL= coNL). Théorème de Reingold : Accessibilité dans un graphe non orienté est dans L (admis). Nondeterministic Space is Closed Under Complementation. Neil Immerman (prix Gödel 1995 pour Neil Immerman et Róbert Szelepcsényi) Undirected Connectivity in Log-Space. Omer Reingold (prix Grace Murray Hopper 2005) Rendu DM2
lundi 22 octobre 2018	TD
lundi 29 octobre 2018	VACANCES
lundi 5 novembre 2018	Alternance Algorithmes alternants. Machines de Turing alternantes. Comparaison entre les classes alternantes et classes déterministes. Jeux booléens et PEEK. Hiérarchie polynomiale. Provably difficult combinatorial games. Stockmeyer and Chandra. Completeness in the Polynomial-Time Hierarchy. Marcus Schaefer and Christopher Umans Rendu DM3
lundi 12 novembre 2018	Fin du cours : oracles. TD
lundi 19 novembre 2018	Problèmes intraitables Diagonalisation. Rappel sur le problème de l'arrêt. Théorème de hiérarchie en espace. Théorème de hiérarchie en temps. Machine universelle efficace. Relativisation. Théorème de Baker, Gill et Solovay : il existe un oracle qui sépare P et NP.
lundi 26 novembre 2018	Complexité des circuits Circuits et familles de circuits. Taille d'un circuit. Classe P/poly. P inclus dans P/poly. Théorème de Karp-Lipton : si NP inclus P/poly, alors PH = Σ2. Parallélisme : hiérarchies AC et NC.
lundi 3 décembre 2018	Rendu DM4 (au choix) TD
lundi 10 décembre 2018	Complexité descriptive Principe : logique du premier-ordre. Exemples : Triangles dans un graphe ; addition. FO = AC0 (admis). FO inclus dans LOGSPACE. Logique du second ordre. Théorème de Fagin. Panorama général : discussion sur clôture transitive, théorème de compacité, localité, etc.
mardi 18 décembre 2018, 10h15	Examen terminal Salle I50 Durée : 2h (+ tiers-temps éventuel)

References

• Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning.
• Dasgupta, S., Papadimitriou, C. H., & Vazirani, U. (2006). Algorithms. McGraw-Hill, Inc.
• Peter van Emde Boas, P. (1997). The convenience of tilings. Lecture Notes in Pure and Applied Mathematics, 331-363.
• Arora et Barak. Computational Complexity: A modern approach.
• Papadimitriou. Computational Complexity.
• Sylvain Perifel. Complexité algorithmique.

Ressources

• Sujet d'examen 2017