Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 12 juin 2018 à 14h00 en B107, Christophe Tollu nous parlera de : Théorie géométrique de la complexité (2/4)

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 : Monday 27 May 2024 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr