La complexité algorithmique est née il y a quasiment 60 ans, quand les chercheurs on commencé à se demander ce que cela signifiait de calculer efficacement. Classifier les problèmes ou fonctions en termes de la quantité de ressources (temps, espace, etc.) nécessaires à les résoudre ou les calculer s’est avéré être une question extrêmement difficile. Ceci a mené les chercheurs à développer une variété remarquable d’approches, employant différentes méthodes et théories mathématiques.
Même si notre laboratoire n’a pas d’équipe dédiée à ce sujet, la complexité algorithmique est présente au LIPN sous différentes formes et dans plusieurs équipes :
- les liens entre logique et complexité sont à la base de l’un des axes de recherche principaux de l’équipe LoVe ;
- analyser la complexité des problèmes d’optimisation, ou leur approximabilité, est un aspect important des travaux de l’équipe AOC ;
- l’étude de complexité en moyenne des algorithmes, approchée par des méthodes combinatoires, est présente dans l’équipe CALIN ;
- les liens entre la complexité algébrique et certains aspects combinatoires de la théorie des représentations sont d’intérêt à la fois pour l’équipe LoVe et CALIN ;
- pour conclure, des questions intéressantes de complexité peuvent potentiellement apparaître dans des recherches de type plus appliqué, comme celles menées par les équipe A3 et RCLN.
L’objectif de l’axe transverse « Complexités » est de fédérer et structurer toutes les recherches mentionnées ci-dessus. Ses activités consistent en :
- l’organisation d’un séminaire regulier, où les membres du LIPN intéressé(e)s à la complexité peuvent apprendre un sujet de façon approfondie, ou partager leur recherche et éventuellement développer des collaborations inter-équipe ;
- l’organisation d’évenements scientifiques avec des invités externes, comme des journées thématiques.