J.-M. Landsberg

La théorie de la complexité algébrique essaie de construire des
algorithmes
rapides pour des taches élémentaires, comme la multiplication des
matrices,
et de déterminer des bornes sur la vistesse de ces algorithmes.
Dans cet exposé on va expliquer comment la géométrie algébrique, la
géométrie différentielle et la théorie des représentations sont utilisées
de nos jours pour s'attaquer à ces questions fondamentales.
On présentera deux problèmes centraux: la variante algébrique de la
conjecture "P vs. NP" et la complexité du produit de deux matrices.
La conjecture "P vs. NP" dit qu'il n'y a pas de solution au problème du
voyageur de commerce plus efficace qu'une recherche naïve. La variante de
Valiant de cette question est liée à l'évaluation de deux polynômes (le
déterminant et le permanent).
L'étude de la complexité de la multiplication des matrices a commencé en
1969 avec la découverte imprévue de Strassen qui prouve que l'algorithme
standard pour la multiplication des matrices n'est pas le meilleur.
Après beaucoup de travaux sur le sujet, une conjecture
choquante, issue de recherche en informatique théorique, attire de plus en
plus d'attention  :  asymptotiquement, ce n'est pas tellement plus
difficile de multiplier deux  matrices que de prendre leur somme.