Tétreault, Étienne
(2019).
« La complexité des immanants » Mémoire.
Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en mathématiques.
Fichier(s) associé(s) à ce document :
Résumé
On étudie dans ce texte les immanants, qui sont des polynômes de degré n en n2 variables définis en fonction des caractères du groupe symétrique. Par exemple, le déterminant et le permanent sont des immanants. Aussi, dans un article datant des années 70, Valiant proposa une première étape pour résoudre le problème P vs NP, appelée hypothèse de Valiant ou problème VP vs VNP, et qui est de montrer
que le permanent ne peut être calculé aussi efficacement que le déterminant. Après avoir rappelé quelques notions de la théorie de la représentation, on fait une courte introduction à la théorie de Valiant. Puis, on étudie le stabilisateur des immanants, pour ensuite considérer leur utilité pour résoudre le problème VP vs VNP. On
considère également une autre technique pour résoudre l'hypothèse de Valiant, appelée théorie géométrique de la complexité, et on voit comment on pourrait utiliser les immanants dans cette théorie.
_____________________________________________________________________________
MOTS-CLÉS DE L’AUTEUR : immanants, hypothèse de Valiant, VP vs VNP, déterminant vs permanent, théorie géométrique de la complexité
RECHERCHER
PARCOURIR
LIBRE ACCÈS
