Thomas Seiller (INRIA), Espace Logarithmique et Permutations
Schedule
- Feb. 15, 2013, 15:30 - 16:00
Abstract
Suite à son travail récent utilisant des algèbres de von Neumann, Girard a proposé une nouvelle approche pour l'étude des classes de complexité. Cette méthode utilise la construction du produit croisé entre une algèbre et un groupe agissant sur celle-ci. Cette construction consiste à internaliser les automorphismes externes représentés par le groupe, et Girard propose de caractériser les classes de complexité par des ensembles d'opérateurs engendrés par ces internalisations.
Nous avons étudié, avec Clément Aubert, le cas de l'action du groupe des permutations des entiers naturels sur un produit tensoriel. Dans un premier travail, nous avons montré que dans ce cas la méthode proposée par Girard permet d'obtenir une caractérisation de la classe co-NL (le complémentaire de l'ensemble des langages décidables par une machine de Turing non-déterministe en espace logarithmique). Afin de prouver ce résultat, nous avons défini la notion de machine à pointeurs qui s'avère être une nouvelle caractérisation de co-NL par des machines abstraites. Plus récemment, nous avons étendu ce travail en définissant un ensemble d'opérateurs caractérisant exactement la classe L (LogSpace).