Colloquium du laboratoire Dieudonné - lundi 19 février à 16:00

La prochaine séance du Colloquium du laboratoire Dieudonné aura lieu le lundi 19 février à 16:00 en salle de conférences. Elle sera suivie d'un goûter en salle café. Notre conférencier sera :

Étienne LOZES (The French Riviera University, Laboratoire d'Informatique, Signaux et Systèmes de Sophia Antipolis, CNRS, http://www.i3s.unice.fr/~elozes/)

et le titre de son exposé sera :

'Introduction à la complexité descriptive'.

Un résumé est le suivant :

La théorie de la complexité algorithmique a pour but de classer les propriétés des structure finies selon la difficulté intrinsèque qu'elles ont à être vérifiées. Les classes de complexités comme P et NP donnent une borne inférieure sur les ressources nécessaires pour CALCULER si une propriété est satisfaite ou non.

La complexité descriptive est une approche alternative de la théorie de la complexité qui se base sur la logique, et qui vise à définir une classe de complexité par rapport aux ressources nécessaires pour ENONCER une propriété. Elle établit une correspondance entre des limitations sur des ressources de calcul (temps, espace, etc) et des limitations sur des ressources syntaxiques (variables, quantificateurs, etc). Par exemple, un théorème de Ronald Fagin stipule que la classe de complexité NP correspond à la classe des propriétés que l'on peut énoncer dans la logique existentielle du second ordre, autrement dit uniquement à l'aide de variables désignant des noeuds de la structure ou des relations entre ceux-ci.

Le problème le plus connu en complexité descriptive est celui, toujours ouvert malgré de récents progrès, de la caractérisation logique de la classe de complexité P, avec en ligne de mire la fameuse question P =? NP.

Dans cet exposé grand public, je rappellerai les notions nécessaires de calculabilité, de complexité, et de logique, puis j'aborderai quelques résultats emblématiques de la complexité descriptive comme le théorème de Fagin, le théorème d'Immerman-Vardi, le théorème d'Immerman-Szelepcsényi, ou encore le théorème d'Abiteboul-Vianu.

Venez Nombreux !

L'équipe Colloquium