| lundi 11 septembre 2017 |
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 18 septembre 2017 |
TD
|
| lundi 25 septembre 2017 |
Complexité en espace
Théorème de Savitch. PSPACE. Pavage d'un corridor. Formules booléennes quantifiées. Jeu de géographie.
|
| lundi 2 octobre 2017 |
TD
|
| lundi 9 octobre 2017 |
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)
|
| lundi 16 octobre 2017 |
TD
|
| lundi 23 octobre 2017 |
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
|
| lundi 6 novembre 2017 |
Fin du cours : oracles.
TD
|
| lundi 13 novembre 2017 |
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 20 novembre 2017 |
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 27 novembre 2017 |
TD
|
| lundi 4 décembre 2017 |
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.
|