Résumé : La théorie géométrique de la complexité (GCT) est un programme de recherche lancé par K. Mulmuley et M. Sohoni aux alentours de 2000 pour attaquer la variante algébrique, due à L. Valiant, de la conjecture centrale de la théorie de la complexité, l'hypothèse de Cook $P \neq NP$. Ce programme substitue aux hypothèses de Cook et de Valiant une conjecture de nature géométrique, à laquelle les formidables outils de la géométrie algébrique et de la théorie des représentations peuvent être appliqués. Dans l'esprit de ses promoteurs, la GCT avait aussi pour but de permettre de démontrer l'existence de minorants de complexité ("lower bounds" en franglais) par la production effective de témoins. Dans ce mini-tutoriel sur la GCT, je présenterai le programme initial de Mulmuley-Sohoni, quelques-uns des développements récents et des obstacles qui sont apparus dans sa réalisation. Aucune compétence particulière en géométrie ou en théorie des représentations n'est requise des participants.

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr