The complexity of computing Kronecker coefficients

The complexity of computing Kronecker coefficients
复制标题

计算克罗内克系数的复杂性

DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Christian Ikenmeyer
Christian Ikenmeyer
中科院分区：
--
文献类型：
--
作者：
Peter Bürgisser;Christian Ikenmeyer

文献摘要

被引文献

相似文献

Kronecker系数是对称群$S_n$的两个不可约表示在张量积分解中的重数。它们也可以解释为两个舒尔多项式在舒尔多项式的基上的内积展开的系数。我们证明了计算Kronecker系数的问题是非常困难的。更具体地说，我们证明了$mathrm{KRONCOEff}$是#$mathrm{P}$-困难的，并且包含在复杂性类$mathm{GAPP}$中。形式上，这意味着$mathm{KRONCOEFF}$的多项式时间算法的存在等价于评估永久数的多项式时间算法的存在。
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.