Complexité algébrique
Cours de recherche (30h de cours, travail
sur des articles scientifiques)
Cours : Pascal Koiran (Pascal.Koiran)
Une grande partie du cours (peut-être la totalité) portera
sur le modèle de calcul algébrique de Valiant. Le principal problème ouvert
dans cette théorie peut être énoncé en une phrase : le permanent d'une matrice
peut il être évalué en un nombre d'opérations polynomial en la taille
de la matrice ? Rappelons que le permanent est un polynôme qui ressemble
beaucoup (du moins en apparence!) au déterminant : dans le déterminant
les signes alternent au gré de la signature de la permutation, mais dans le
permanent il n'y a que des signes +.
Il s'agit en quelque sorte d'une version algébrique du problème “P=NP ?”.
Le rôle de P est joué dans la théorie de Valiant par la classe VP des familles
de polynômes pouvant évalués en un nombre polynomial
d'opérations arithmétiques. Le rôle de NP est joué par une classe
appelée VNP, et le permanent est VNP-complet.
Le cours sera consacré en grande partie à l'étude de ces deux classes.
On abordera peut-être également le modèle de Blum-Shub-Smale,
dans lequel en plus des opérations arithmétiques on s'autorise
à faire des comparaisons.
Voici quelques livres disponibles à la bibliothèque sur ces sujets.
-
Sur Valiant: "Completeness and reduction in algebraic complexity
theory”, de Buergisser.
- Sur BSS: “Les petits cailloux”, de Poizat.
- “Complexity and real computation” de Blum, Cucker, Shub et Smale.
On peut trouver des références supplémentaires sur la page du cours
(http://perso.ens-lyon.fr/pascal.koiran/complexite_algebrique.html).