The complexity of computing Kronecker coefficients

Résumé : Les coefficients de Kronecker sont les multiplicités dans la décomposition du produit tensoriel de deux représentations irréductibles du groupe symétrique. On peut aussi les voir comme les coefficients du développement du produit interne des polynômes de Schur. Nous montrons que le problème $\mathrm{KRONCOEFF}$ de calculer les coefficients de Kronecker est très difficile. Plus précisément, nous prouvons que $\mathrm{KRONCOEFF}$ est #$\mathrm{P}$-dur et que $\mathrm{KRONCOEFF}$ est dans la classe de complexité $\mathrm{GapP}$. Cela veut dire qu'il existe un algorithme pour $\mathrm{KRONCOEFF}$ s'exécutant en temps polynomial si et seulement s'il existe un algorithme pour l'évaluation du permanent s'exécutant en temps polynomial.
Type de document :
Communication dans un congrès
Krattenthaler, Christian and Sagan, Bruce. 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), 2008, Viña del Mar, Chile. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), pp.357-368, 2008, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01185157
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 19 août 2015 - 11:42:29
Dernière modification le : jeudi 11 mai 2017 - 01:02:52
Document(s) archivé(s) le : vendredi 20 novembre 2015 - 10:32:43

Fichier

dmAJ0131.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185157, version 1

Collections

Citation

Peter Bürgisser, Christian Ikenmeyer. The complexity of computing Kronecker coefficients. Krattenthaler, Christian and Sagan, Bruce. 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), 2008, Viña del Mar, Chile. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), pp.357-368, 2008, DMTCS Proceedings. 〈hal-01185157〉

Partager

Métriques

Consultations de la notice

63

Téléchargements de fichiers

251