Responsables : A. Durand, M. Hils, P. Simonetta, S. Todorcevic. Pour recevoir le programme par email, écrivez à : malod_at_logique.jussieu.fr.
Tous les lundis ouvrables de 14h à 15h15 : Université de Paris 7, site de Chevaleret (175 rue du Chevaleret, Paris 13 ème), Salle 0D9 (au rez-de-chaussée au fond à droite).
Le séminaire général est suivi d'un "thé logique" (à partir de 15:30, vers la machine à café au 5e) avec biscuits, thé et café. Venez nombreux!
Lundi 15 février 2010 : Bruno Poizat (ICJ, Université Lyon 1) Transformations
Une fonction est par définition une application de {0, 1}^n dans {0, 1},
ou plus généralement dans un corps fini k , ou plus généralement encore
dans un anneau A finiment engendré. Comme toute fonction f s'exprime
comme un polynôme à coefficients dans A, nous appelons complexité de f le nombre minimal d'additions et de multiplications qu'il faut pour
l'obtenir à partir de variables et de constantes.
Nous appelons transformation une application linéaire inversible entre
fonctions, qui satisfait à la condition de Fubini : T(f).T(g) = T(f.g)
quand les uples de variables de f et de g sont disjoints. Un exemple
de transformation est la duale inverse, qui décrit les coefficients du
polynôme canonique de f. Nous étudierons les effets des transformations
sur la complexité des fonctions.
Cet exposé s'adresse a des mathematiciens normaux, et ne suppose aucune
connaissance préalable sur les classes de complexite de calcul (P, NP, #P,
PSPACE, etc.).
Exposés précédents : Années
00-01,
01-02,
02-03,
03-04,
04-05,
05-06,
06-07,
07-08,
08-09,
09-10.
Page maintenue par G. Malod