Partager cette page :

Théorie de la complexité

Semestre Semestre 1
Type Facultatif
Nature UE

Objectifs

Le cours est une initiation à la théorie de la complexité. En pratique, les problèmes combinatoires (en vérification de programmes, en compilation, en robotique, etc.) se résolvent à l'aide d'outils comme des solveurs SAT, des model-checkers, des planificateurs, etc. Ainsi, connaître la complexité intrinsèque d'un problème justifie la pertinence de l'utilisation d'un de ces outils. Un des objectifs du cours est de donner les méthodes pour démontrer des résultats de complexité. Un autre objectif est de donner un panorama des problèmes ouverts de ce domaine. Plus largement, le cours offre des bases solides pour manipuler les concepts mathématiques formels de l'informatique.


Contenu

- Machines de Turing. Classes de complexité en temps. P et NP. Réduction polynomiale. NP-complétude. Théorème de Cook. Théorème de Ladner.

- Classes de complexité en espace. PSPACE. Théorème de Savitch. PSPACE-complétude. Formule booléenne quantifiée.

- Classe L et NL. Réduction en espace logarithmique. Accessibilité dans un graphe. Théorème d'Immerman-Szelepcényi. NL = co-NL.

- Insolubilité. Diagonalisation. Théorèmes de hierarchie. Relativisation. Oracles.

- Machines alternantes. Théorème de Chandra, Kozen et Stockmeyer. Hiérarchie polynomiale.

- Circuits. Uniformité. Classes AC et NC. Parité. Théorème de Karp-Lipton.


Mise à jour le 12 avril 2018