体积系数的计算复杂性及其在乘法张量边界秩下界中的作用

体积系数的计算复杂性尼克·菲舍尔马克斯·普朗克信息学研究所，德国萨尔布吕肯计算机科学研究生院克里斯蒂安·伊肯迈耶利物浦大学在这两篇文章中，Bürgiser和I kenmeyer（STOC2011，STOC2013）使用Mulmuley和Sohoni（Siam J COMPUT 2001，2008）的几何复杂性理论（GCT）方法的改编来证明矩阵乘法张量的边界秩的下界。一个关键因素是关于某些克罗内克系数的信息。虽然张量是GCT思想的一个有趣的测试平台，但其遥远的目标是分离代数复杂性类。克罗内克系数在这种情况下的作用由所谓的体积系数（plethysm coefficients）承担：这些是多项式空间的坐标环中的多重性尽管已知Kronecker系数的几个硬度结果，但几乎没有关于计算体积系数或甚至确定其正性的复杂性的在本文中，我们证明了确定容积系数的正性是NP-困难的，计算体积系数很难事实上，即使体积系数的内部参数是固定的，这两个问题仍然很难。以这种方式，我们获得内部与外部的对比：如果体积系数的外部参数是固定的，则体积系数可以在多项式时间内计算系数此外，我们推导出新的上下界，在特殊情况下，甚至组合描述的体积系数，我们认为是独立的利益。我们的技术以比Ikenmeyer，Mulmuley和Walter最近关于Kronecker系数的工作更精细的方式使用离散断层扫描（Comput Compl 2017）。这使得我们的工作第一个应用离散断层扫描技术的体积系数的研究。令人惊讶的是，这种解释也导致某些体积系数和克罗内克系数之间的新等式。电子邮件：nfischer@ mpi-inf. mpg. de。†电子邮件：christian. ikenmeyer@liverpool.ac.uk。本研究部分是作者在萨尔布鲁克纳的马克斯计划研究所进行的。 作者得到了D FG基金IK 116/2-1的支持。arXiv：2002.00788v1 [cs.CC] 2020年211介绍几何复杂性理论（Geometric Complexity Theory，GCT）是一种使用代数几何和表示理论来分离Valiant代数复杂性类的方法。 这些想法是由Mulmuley和Sohoni在[MS01，MS08]中介绍的。该框架的第一个实现证明了矩阵乘法张量[BI11，BI13b]的边界秩的下界。在这些论文中，克罗内克系数起着关键作用，因为它们是张量空间坐标环中的重数。虽然这一系列的研究结果是对GCT思想的一个有趣的测试案例，但最终目标仍然是分离代数复杂性类，即多项式（族）的某些集合。 从张量转换到多项式，克罗内克系数的作用在[BI11，BI13 b]中，现在由体积系数（参见例如[BI18，Sec. 12.4（i）]）。体积系数是“GCT 7”[Mul 07]的主要主题，在GCT出版物[KL 14，Kum15，Bur 16，BHI 17]中也有突出的内容。本文的主要研究对象是体积系数，其次是克罗内克系数.这两种类型的表示理论的系数不仅是重要的GCT，但他们在代数组合学的基本对象事实上，在1999年，理查德Stan- ley强调寻求组合描述的体积系数的问题9在他的调查即使GCT要求比较这些（和相关）系数（参见例如，[Ike12，附录]），这两个系数大多是独立研究的但最近这种情况开始改变，例如，美国数学学会2016年秋季东部会议举行了一次关于“表示论中的Plethysm和Kronecker产品”的特别会议，以及2020年据我们所知，唯一的文件，使这两种系数之间的不平等是[曼11，IP17，BIP19]2。在GCT中，这两个系数不仅作为张量或多项式空间的坐标环中的重数，而且它们还作为描述重要群轨道的坐标环的重数的非负公式中的项出现：体积系数作为变量乘积轨道的坐标环中的重数的非负公式中的项出现（[Lan17，Sec.9.2.3]）、幂和多项式（[IK19]）、单位张量（[Ike19， Sec. 3.7]），以及永久多项式（[BLMW11，等式11]）。（5.5.2）]），而克罗内克系数出现在行列式多项式轨道的坐标环中的多重数的非负公式中[BLMW 11，方程11]。（5.2.6）]，永久多项式（[BLMW11，方程（5.5.2）]，体积系数和克罗内克系数都出现在这个公式中），矩阵乘法张量[BI11，Thm. 5.3]，单位张量（[Ike19， Sec. 3.7]，体积系数和克罗内克系数都出现在这个公式中），以及矩阵幂多项式的迹[GIP17，Thm 2.10]。在理论物理学中，体积和克罗内克系数分别与不可区分和可区分粒子的量子边缘问题密切相关，参见例如[CHM07]和[CDKW 14，Sec.7]，研究了系数的渐近正性虽然克罗内克系数计算的#P-困难可以追溯到1在计算复杂性理论的语言中，“寻找组合描述”通常被解释为“证明从其参数列表中计算系数的函数在复杂性类#P中”。[Mul 07]列出了可能暗示#P中的约束的示意图，从而提供了Stanley的问题9。2[Mul09]写道，[…]基本体积系数的特殊情况2Σ0K[BI 08，BOR 09]，最近的文章[IMW 17]证明了判定Kronecker系数为正的NP这是GCT程序的一个挫折，因为最初推测Kronecker正性将在多项式时间内可判定，与众所周知的Littlewood-Richardson系数的方式大致相同：即使Littlewood-Richardson系数的计算是#P-完全的[Nar 06]，Littlewood-Richardson系数的正性也可以使用线性规划（另见[MNS 12]）在多项式时间内判定[DLM 06]，甚至使用组合最大流算法[BI 13 a]。这样的结果将使得对障碍物的搜索（即，系数之间的不平等）更容易。本文证明了体积系数正性判定的NP-困难性（定理3.1）和体积系数计算的P -困难性（定理3.2）。在我们的工作之前，甚至不知道体积系数的计算的#P-困难。事实上，与用于证明Kronecker系数决定正性的NP -困难性的方法相比，我们的还原是相当微妙的[IMW 17]。本文结构第二节从表征理论的角度解释了必要的背景。第3节陈述了我们的主要硬度结果，并将它们与已知的有效可计算子情形进行对比。第4节是我们简化的第一个重要步骤：我们证明了体积系数的内部参数可以固定为3。第5节将体积系数问题的一个有趣的子情形转化为离散层析成像中的一个问题。在第6节中，我们使用这个层析描述来设计一系列的减少，最终证明我们的硬度结果。第7节和第8节包含独立感兴趣的结果：第7节突出了新的密切联系克罗内克系数，而第8节包含更多的组合描述的体积系数。最后，第9节使用经典结果提供了一个算法，该算法将计算体积系数的问题放在复杂性类GapP中。2表示论的基本原理我们使用的体积和克罗内克系数的定义需要一些基本的代数几何和表示理论，例如可以在标准教科书[Kra85，FH91，Sag01]中找到。必要的材料也可以例如在[Lan11，Ch.6]。复合λ是非负整数λ=（λ0，λ1，. . . ），我们总是通过省略尾随零来将其视为有限的。 如果元素是非递增的，那么我们称λ为一个划分。 A分区λ通常以其Young图表示，这是一个左上对齐的数组，其中包含λi框，第i行。 例如，（3， 1）与Young图相同. 在那次演讲中将λ0表示为λ的宽度，将非零条目的数量表示为λ的高度是有意义的。 我们参考了|λ|：= iλi在λ的杨氏图中的盒子作为λ的大小。 如果λ为高度1，那么我们称λ为1行分区，同样，如果λ的宽度为1，那么λ是1列分区。最后，设λ的转置λt表示通过交换行和列获得的划分。例如，（3，1）t=（2，1，1）被描述为。设V是有限维复向量空间。 有一个规范的一般行动V上的线性群GL（V）由gv：=g（v）给出，对所有g∈GL（V），v∈V。对于组合物λ，如果diag（α0，. . .，αk）v=αλ0· · ·αλkv，则我们说v是权向量λ。 注意对所有矩阵m∈gl（V）：=CdimV×dimV，有Id+εm∈GL（V），其中Id是dimV× dimV单位矩阵。我们说V允许李代数gl（V）的一个作用，定义为mv：= limε→0ε−1（（Id +εm）v−v），对所有m∈gl（V），v∈V. 对于ij，<3NmνNm！VMV（如果）。通过一些众所周知的对偶性[Car90，Man98，M MM15]，我们可以将aboveλλλλ定义提升算子Ei，j∈gl（V）为在位置（i，j）上只有一个1而在其它位置上都为零的矩阵。一个权向量v的权值为λ，如果v在所有提升算子的作用下为零，则称v为最高权向量。在这种情况下，λ保证是一个分区。 众所周知，GL（V）的不可约多项式表示的特征在于其唯一的（按比例）最高权重向量，其进而由至多dim V处的高度的分区索引。ν型不可约GL（V）-表示称为Weyl模，记为的SV。Weyl模SνV的构造如下。给定任意GL（V）-表示W（例如W=V ） ， 存 在 其 m次 张 量 幂 上 的 自 然 线 性 GL （ V ） -作 用 量mW 由 下 式 给 出 ：g（ w1<$w2<$··<$wm）：=（gw1）<$（gw2）<$··<$（ gwm）和线性延拓。我们定义SνW为Schur函子S的象 将W映射到它的m次张量幂W然后投射到第ν个同型成分上，w›→1π∈Smχν（π）πw，其中χν是对称群Sm的类型ν的不可约表示的特征标。 例如，如果ν=（m），则SνV是m阶对称张量的向量空间，我们用Sym mV表示。若ν=（1，1，. . .，1）的大小为m，则SνV是m阶交错张量的向量空间，记为mV。体积描记法是Sµ到SνV的应用。 上面的讨论表明这个空间SµSνV：= Sµ（SνV）是一个GL（V）-表示。由于GL（V）是可约的，所以每个有限维GL（V）-表示都分解为不可约GL（V）-表示的直和SµSνV=（SλV）<$pλ（µ，ν）。λ非负整数pλ（μ，ν）称为广义体积系数。其中μ=（n）和ν=（m）的情况是特别有趣的，所以我们写一个λ（n，m）：=pλ（（n），（m）），它是Sym nSym mV中λ型的重数。在文献中，系数aλ（n，m）通常被称为体积系数。我们引入对偶体积系数bλ（n，m）作为一般体积系数的另一种特殊情况，定义为：SymnSymmV=M（SλV）<$aλ（n，m） 和^nSymmV=M（SλV）<$bλ（n，m），（2.1）也就是说，通过将Young图μ和ν限制在单行（在Sym的情况下）或单列，在交换Sym和.2.2 Fact（[Car90，Man98，MM15]）如果m是奇数，则：^n^mV=M（SλV）<$aλt（n，m） 和Symn^mV=M（SλV）<$bλt（n，m），（2.3）λ λ而在m是偶数的情况下^n^mV=M（SλV）<$bλt（n，m） 和Symn^mV=M（SλV）<$aλt（n，m）。（2.4）（注意，在这些分解（式2.3）和（式2.4）中，λ在aλt（n，m），bλt（n，m）中转置，而不是在（式2.1）中转置。）4λ∈A（n）不λ∈B（n）3主要结果：体积系数的复杂性为了确定计算一般体积系数pλ（μ，ν）的难度，当然只关注有趣的特殊情况aλ（n，m）和bλ（n，m）就足够了。为此，我们从复杂性理论的角度研究了以下问题3。问题（P LETHYSM）给定一个划分λ和两个整数n和m，输出aλ（n，m）。给定一个划分λ和两个整数n和m，如果aλ（n，m）>0，输出“accept”，否则输出“reject”。给定一个划分λ和两个整数n和m，输出bλ（n，m）。给定一个划分λ和两个整数n和m，如果bλ（n，m）>0，输出“accept”，否则输出“reject”。我们注意到aλ（n，2）和bλ（n，2）的计算在多项式时间4内是可能的，所以我们只需要处理m≥3的情况。我们特别感兴趣的是参数m或n之一固定的情况。因此，对于上面的每一个问题，我们都定义了这样的版本，其中m和n分别通过在问题名称后分别添加（INNER=m）和（OUTER=n例如，P LETHYSM（INNER =3）是“给定λ和n，计算λ（n，3）”的问题。我们注意到， P淋巴细胞活性称为在[KM16a]中，这个问题被标记为“高度非平凡”。我们的主要结果使这个直观的陈述精确。我们证明了PLETHYSM P活性是NP-困难的：3.1 定理P LETHYSM（INNER = m）和DUAL PLETHYSM（INNER=m）对于任何固定的m≥ 3。 特别是，P淋巴细胞的P活性和双P淋巴细胞活性是NP难的。通过对证明的深入分析，证明PLETHYSM是#P-困难的：3.2 定理PLETHYSM（INNER=m）和DUAL PLETHYSM（INNER=m）对于任意固定的m≥ 3。特别是，P LETHYSM和双P淋巴结 #P-硬。考虑定理3.1和定理3.2，如果我们固定外部参数而不是内部参数，我们得到一个有趣的复杂性理论对比，如下面的命题所示，其证明可以从[KM 16a]5中提取。3.3 命题P淋巴结（外部=n）和双侧P淋巴结（外部=n）是在P任何固定的;固定的 更一般地，计算pλ（μ，（m））可以在多项式时间内完成，如果|μ|是固定的.定理3.1（如果m是固定的，那么即使确定λ（n，m）的正性也是NP困难的）和命题3.3（如果n是固定的，那么即使计算λ（n，m）的精确值也可以在多项式时间内完成）之间复杂性的这种惊人差异可以解释为什么它是NP困难的。3在所有问题中，输入可以用二进制或一进制编码，因为这对我们下面的结果没有区别。硬度的结果仍然适用于一元编码，而多项式时间算法仍然适用于二进制编码。[4][Sta99a，Wey03，提案2.3.8，提案2.3.9]，Sym nSym2V分解为LSλV对于A（n）={λ的大小为2n：每个λi都是偶数};类似地，我们有VnSym2V=L SλV，其中B（n）={λ的大小为2n：如果λi≥i，则λi=λi+1}。检验隶属度λ∈An和λ∈Bn都可以进行在多项式时间内，|λ|.5 [KM16a]表明，对于任何固定分区μ，函数（λ0，. . .，λ|µ| −1）›→pλ（µ，（m））有一个常数大小的算术公式（模运算），其输入是λi;参见arXiv版本[KM 16 b]的附录中的详细说明。5VV≤V被认为是更难以获得关于aλ（n，m）的精确结果，其中nm比较对于其中mn的情况，参见例如[Wei90，TC92，KM16a，KM18，KL 19]作为证据。此外，#P-硬度结果导致复杂性类GapP的完整性结果-即，可由非确定性多项式时间图灵机实现的所有计数问题的类，其中输出被解释为接受计算路径的数量减去拒绝计算路径的数量[FFK 94]。3.4 定理P定理、 DUAL P定理及广义体积系数的计算问题ficients是GapP-完全的。定理3.4的证明在第9节中给出。4将内部参数固定为m= 3为了最终证明定理3.1和3.2，我们初步证明了m= 3情况的证明难度是足够的：4.1 引理设m是固定的。给定一个以一元编码的分区λ，我们可以计算分区π和πJ，使得aλ（n，m）=bπ（n，m+1）和bλ（n，m）=aπ′（n，m+1）.特别地，假设判定aλ（n，3）和bλ（n，3）两者的正性已经是NP困难的，则对于每个固定的m≥3，判定体积系数aλ（n，m）或bλ（n，m）的正性也是NP困难的为了证明引理4.1，我们利用另一个事实：4.2 Fact（[MM 15]）设ν是n的一个划分，设λ是n·m的一个划分，其宽度至多为n，设π是在λ前面加上一行宽度为n的划分。 则不可约分量SλV在SνmVe中的重数等于不可约分量SπV在Sνm+1V中的重数。引理4.1的证明我们只说明第一个主张，第二部分是类似的。设一个分区λn·m的值。事实2.2得出aλ（n，m）等于不可约表示的重数站SλtV 在SνVm 其中v是由单个如果m是偶数，则宽度为n的行，否则v等于长度为n的列。如果λt的宽度>n，那么我们立即推出aλ（n，m）=0。 因此，假设λt的宽度为n，并通过在λt前添加一行宽度为n的行来构造一个划分πt。根据事实4.2，我们推断多重性Sπt在Sνm+1的分解中等于a最终得到aλ（n，m）=bπ（n，m+1）.现在我们来处理m= 3的情况。（n，m），通过再次应用事实2.2，我们5体系数的离散层析组合描述我们在第3节中的结果是基于一个新的组合描述的体积系数的子情况下，基于新的组合下限和上限的体积系数。我们认为，上下界以及组合描述是独立的兴趣。通过[i，j]，我们表示范围{i，. . .，j}N.定义C：={（x，y，z）：x>y>z}<$N3为开锥，C={（x，y，z）：x≥y≥z}<$N3为闭锥. 一个有限集P∈C称为开锥中的一个点集。一个有限集P∈C称为闭锥中的一个点集。点集Pλ6Σ+Σλ^V^Vn+3V{}t VnV3λλλλλλSymV的权λ的权子空间。 回想一下，B （n，3）精确计算这样集合P，因此bλ（n，3）等于权-λ子空间的维数。 而且由于Sym在开锥中的金字塔称为开锥中的金字塔，如果对所有（x，y，z）∈P和所有（xJ，yJ，zJ）∈C，其中xJ≤x，yJ≤y，zJ≤z，我们有（xJ，yJ，zJ）∈P。 类似地，闭锥中的点集P称为闭锥中的棱锥，如果对于所有（x，y，z）∈P和所有（xJ，yJ，zJ）∈C，其中xJ≤x，yJ≤y，zJ≤z，我们有（xJ，yJ，zJ）∈P。设P是开锥或闭锥上的点集。边际和S（P）是由下式定义的数列：Si（P）：=（x，y，z）∈Pδx，i+δy，i+δz，i，（5.1）其中，如果i=j，则δi，j= 1，否则δi，j= 0。 注意|S（P）|：=i Si（P）= 3 |P|.5.2 定义设λ是3n的一个划分.我们定义：• a−λ（n，3）为整数λt的整数环中的pyramids的个数，• a+（n，3）为具有和极大值λt的顶点集的个数，• b−λ（n，3）作为具有和-整数λ的双dc中的pyramids的数目，• bλ（n，3）表示闭锥中和边际λ的点集个数。下一个定理将体积系数与我们刚刚定义的组合概念联系起来。5.3 定理设λ是3n的一个分拆。然后又道：a−（n，3）≤aλ（n，3）≤a+（n，3）和b−（n，3）≤bλ（n，3）≤b+（n，3）。证据设X0，X1，. . .，Xk−1是V = Ck的有序基。在Cy>z}为开锥中的完全棱锥，类似地称Pr：={（x，y，z）：x+y+z≤r，x≥y≥z}为闭锥中的完全棱锥。 对于所有r，我们有β（|P r|）= B（Pr）. 此外，β（n）是这些值之间的分段线性插值类似地，β（n）是β（|Pr|）= B（Pr）.以下引理的证明是Brunetti，Del Lungo和G′era r d[BDLG 01]对非对称3D-X-RAY问题给出的证明的仔细改编。 粗略地说，三角形是将二维网格Gr嵌入到完整金字塔的第r层中 。6.4 引理设P ∈ C有大小|P |= n. 则P有坐标和B（P）=β（n）当且仅当Pr−1<$P<$Pr对于某个r。类似地，设PC为|P|=n.则P有坐标和B（P）=β（n）当且仅当Pr−1<$P<$Pr对于某个r。证据 通过直接计算很容易看出，所有点集P r−1<$P<$P r都有B（P）= β（n），因为P\P r−1中的每个点都有相同的坐标和r（即，P\Pr−1<$Gr）。另一个方向是直观的，通过下面的论证：只要P包含一个“洞”，那么我们可以通过将外部点移到更靠近原点的位置来填充这个洞。但是我们减少了P的坐标和。更正式地说：假设P在所有相同大小n的集合<$C中具有最小坐标和。 我们选择r为最大值，使得Pr−1<$P，并且为了矛盾起见，假设P/<$P r，即，存在某个（x，y，z）∈P\Pr.此外，存在一些（xJ，yJ，zJ）∈ Pr\P，因为否则P <$Pr，这与我们选择r的方式相矛盾。我们构造集合PJ：= P<${（xJ，yJ，zJ）} \ {（x，y，z）};清楚地|PJ|为|P|= n. P的坐标和由下式限定B（PJ）=B（P）−（x+y+z）+（xJ+yJ+zJ）rx`≤rx12^^^^ ^您的位置：^^ ^您的位置：^ ^您的位置：^^^^^^ ^您的位置：6.5LemmaFixsomer. Letλ^∈N[0，r]be使得re存在n，|λ^|= 3n和B（λ^）= rn。ZYG1G2GrX图3可视化了如何在三维空间中排列网格Gr;红色区域表示与C（或C，通过限制到内部）的交点。约简的基本步骤是将集合P<$Gr嵌入金字塔P：=Pr−1<$P^的最顶层。这与β（n）的定义相矛盾。这个证明对C完全类似。现在通过将Gr嵌入三维空间来进行约简任何解决方案给定的（S斜）对称2D-X-R层实例的P层被解释为在其下完全填充的金字塔P=Pr−1<$P;图3可能会给出一些进一步的直觉如何在三维空间中观察对称二维X射线我们在下面的引理中详细说明了构造（即， λ（1）不直接表示为S对称2D-X-R（例如）。 Letλ：=S（Pr−1）+λ^.B = B（|P r−1|+ n）之间存在一一对应关系和-边际λ的点集P <$Gr<$C。如果我们考虑开锥C中的点集Pr−1和Pr，以及S KEW-S对称问题，同样的陈述也成立。在这种情况下，λ：= S（Pr−1）+ λ。证据1）A = B（A = B）+B（B = B）+B（|Pr−1|）+rn=β（|Pr−1|+n）。所声称的一一对应关系如下：对于P <$C，边际和λ = S（Pr−1）+ λ，我们知道（引理6.4），对于某个P<$C<$Gr，P = Pr −1 <$P。集合P有和边际λ。相反，如果某个集合P有和边际λ，则集合P：=Pr−1<$P有和边际S（Pr−1）+λ=λ。两个映射P<$→P和P<$→P都是逆映射，从而完成了证明。在应用明显的变化之后，证明也适用于开锥C。引理6.3的证明给定#S对称2D-X-R AY实例λ