THX - Théorie de la complexité

Master 1 - ENS Rennes - Année 2021/2022

Cours + travaux dirigés : François Schwarzentruber

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)
Catalog of reductions. TD

Complexité en espace

Théorème de Savitch.
PSPACE.
Pavage d'un corridor.
Formules booléennes quantifiées. TD

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) TD

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
TD

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.

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. TD

Complexité descriptive (non fait)

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.

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.