The complexity of computing Kronecker coefficients - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2008

The complexity of computing Kronecker coefficients

Résumé

Kronecker coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the symmetric group $S_n$. They can also be interpreted as the coefficients of the expansion of the internal product of two Schur polynomials in the basis of Schur polynomials. We show that the problem $\mathrm{KRONCOEFF}$ of computing Kronecker coefficients is very difficult. More specifically, we prove that $\mathrm{KRONCOEFF}$ is #$\mathrm{P}$-hard and contained in the complexity class $\mathrm{GapP}$. Formally, this means that the existence of a polynomial time algorithm for $\mathrm{KRONCOEFF}$ is equivalent to the existence of a polynomial time algorithm for evaluating permanents.
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.
Fichier principal
Vignette du fichier
dmAJ0131.pdf (306.5 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01185157 , version 1 (19-08-2015)

Identifiants

Citer

Peter Bürgisser, Christian Ikenmeyer. The complexity of computing Kronecker coefficients. 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), 2008, Viña del Mar, Chile. pp.357-368, ⟨10.46298/dmtcs.3622⟩. ⟨hal-01185157⟩

Collections

INSMI TDS-MACS
116 Consultations
869 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More