Des invariants de cohomologie pour la complexité ?

Carte non disponible

Date/heure
Date(s) - 27/11/2014
11 h 00 min - 12 h 00 min

Catégories Pas de Catégories


J’exposerai des résultats récents à l’intersection entre mes travaux sur les graphes d’interaction et ceux concernant la complexité.
Mon travail sur les graphes d’interaction m’a mené à une construction systématique de modèles de la logique linéaire basée sur la notion de « graphage » — des réalisations de graphes par des fonctions mesurables. Intuitivement, un graphage est un graphe dont les sommets sont des ensembles mesurables et les arêtes sont « réalisées » par des fonctions mesurables. Ces modèles sont caractérisés par un monoide de fonctions (mesurables) qui décrit les différents manières de réaliser une arête.
Je montrerai que le choix de ce monoide correspond à imposer des contraintes de complexité. Cette correspondance est illustrée par l’obtention de modèles de MALL avec des exponentielles (très) faibles où le type des prédicats sur les entiers binaires !Nat_2 ⊸ Bool caractérise des classes de complexité telles que les languages réguliers, L (logspace), NL, Ptime.
Ces résultats permettent d’envisager l’utilisation d’invariants de cohomologie pour étudier les classes de complexité.

[http://www.ihes.fr/~seiller/]

Olivier CHABROL
Posts created 14

Articles similaires

Commencez à saisir votre recherche ci-dessus et pressez Entrée pour rechercher. ESC pour annuler.

Retour en haut
Secured By miniOrange