4 février 2019
Sébastien Tavenas (LAMA - Université de Savoie) Le problème “P=NP?” est largement reconnu comme le principal problème ouvert en informatique théorique. Étant donné la difficulté de ce problème, des versions algébriques, un peu plus faibles, ont été définies. On espère alors que des méthodes géométriques ou algébriques seront plus faciles à appliquer. On s’intéressera à une version “VP=VNP?” proposée par Leslie Valiant à la fin des années 70 où on étudie la complexité de l’évaluation des polynômes. Le contenu algorithmique de ce problème peut être résumé en une phrase : est-il possible d’évaluer le permanent d’une matrice n*n en un nombre d’opérations arithmétiques polynomial en n ?
On présentera ce problème, puis on s’intéressera plus particulièrement à une de ses caractéristiques (connue depuis 1983) qui le différencie de son homologue Booléen : tout polynôme qui est efficacement calculable est aussi efficacement parallélisable. Ainsi, pour obtenir des bornes inférieures dans le cas général, il est suffisant de trouver des bornes “assez bonnes” en petite profondeur. On finira alors par exhiber des bornes inférieures (malheureusement insuffisantes pour résoudre VP=VNP) en profondeur 3 et 4.