The complexity of computing Kronecker coefficients

Abstract. Kronecker coefficients are the multiplicities in the tensor product decomposition of two irreducible repre-sentations 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 complexite ́ 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