| mardi 10 septembre 2019 à 10h15, salle 24 |
IntroductionProblè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) Catalog of reductions. |
| mardi 17 septembre 2019 | TD |
| mardi 24 septembre 2019 |
Complexité en espaceThéorème de Savitch. PSPACE. Pavage d'un corridor. Formules booléennes quantifiées.Rendu DM1
|
| mardi 01 octobre 2019 | TD |
| mardi 8 octobre 2019 |
Complexité en espace logarithmiqueL 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
|
| mardi 15 octobre 2019 | TD |
| mardi 22 octobre 2019 |
AlternanceAlgorithmes 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 UmansRendu DM3
|
| mardi 29 octobre 2018 | VACANCES |
| mardi 5 novembre 2019 | Fin du cours : oracles. TD |
| mardi 12 novembre 2019 |
Problèmes intraitablesDiagonalisation. 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. |
| mardi 19 novembre 2019 |
Complexité des circuitsCircuits 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. |
| mardi 26 novembre 2019 |
Rendu DM4 (au choix)
TD
|
| mardi 3 décembre 2019 |
Complexité descriptivePrincipe : 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 ?? décembre 2019, ?? |
Examen terminalSalle I50 Durée : 2h (+ tiers-temps éventuel) |