The complexity of computing Kronecker coefficients
Peter Bürgisser, Christian Ikenmeyer
Abstract
Kronecker coefficients are the multiplicities in the tensor product
decomposition of two irreducible representations of the symmetric
group Sn. 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 KronCoeff of computing
Kronecker coefficients is very difficult. More specifically, we prove
that KronCoeff is #P-hard
and contained in the complexity class GapP. Formally, this means
that the existence of a polynomial time algorithm for KronCoeff
is equivalent to the existence of a polynomial time algorithm for
evaluating permanents.
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 KronCoeff de calculer les coefficients de Kronecker est très difficile. Plus précisément, nous prouvons que KronCoeff est #P-dur et que KronCoeff est dans la classe de complexité GapP. Cela veut dire qu'il existe un algorithme pour 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.
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 KronCoeff de calculer les coefficients de Kronecker est très difficile. Plus précisément, nous prouvons que KronCoeff est #P-dur et que KronCoeff est dans la classe de complexité GapP. Cela veut dire qu'il existe un algorithme pour 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.
Full Text: GZIP Compressed PostScript PostScript PDF