La théorie de la complexité est un domaine des mathématiques et de l'informatique fondamentale qui cherche à montrer des bornes inférieures sur le niveau de ressources nécessaire pour résoudre un problème algorithmique. Les types de ressources peuvent être extrêmement variés : le temps de calcul, bien sûr, l'espace, le coût de communication, le niveau d'aléatoire, les langages dans le cadre d'une description logique, la longueur ou la forme des preuves dans un système formel, le nombre d'opération arithmétiques, la taille d'une description d'une structure de données auxiliaire, et bien d'autres mesures...
Dans bon nombre de contexte, prouver des bornes inférieures inconditionnelles s'avère extrêmement difficile et les recherches se sont focalisées sur la recherche de bornes inférieures sous hypothèses algorithmiques, la plus ancienne d'entre elles étant la théorie de la NP-complétude.
La théorie de la complexité étudie des problèmes provenant de nombreaux domaines des mathématiques et de l'informatique : bases de données, intelligence artificielle, bioinformatique, recherche opérationnelle, calcul quantique,... De plus elle emprunte des outils et des résultats venant d'horizons variés : traditionnellement de combinatoire et de logique mais aussi de physique, théorie de l'information théorie du codage ainsi qu de géométrie algébrique, analyse de Fourier et théorie des groupes. Cette multiplicité d'objectifs et de points de vues rendent la complexité très riche et diverse.
L'objectif de ces journées de complexité est d'offrir un panorama sur quelques spects de la recherche en théorie de la complexité, mais aussi de rassembler la communauté des chercheurs travaillant dans cette thématique, notamment en France. Elles permettront aux participants de présenter leur travaux et d'échanger à la fois sur les questions et les techniques venant de domaines différents.
Orat·eur·rice·s invité·e·s
Martin Grohe (RWTH Aachen University)
Sophie Laplante (Université Paris Cité)
Jakob Nordström (University of Copenhagen & Lund University)
Sébastien Tavenas (CNRS, Université Savoie Mont Blanc)
Chargement... 
