Algebraic branching programs, border complexity, and tangent spaces
Algebraic branching programs, border complexity, and tangent spaces
复制标题
代数分支程序、边界复杂性和切线空间
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Nitin Saurabh
中科院分区：
文献类型：
--
作者：
M. Bläser;Christian Ikenmeyer;M. Mahajan;Anurag Pandey;Nitin Saurabh
Nisan在1991年证明了计算非交换多项式的最小非交换单（源，汇）代数分支程序（ABP）的宽度由特定矩阵的秩给出。这意味着ABP宽度复杂度最多为k的非交换多项式集合是Zerkiki闭的，这是几何复杂度理论中的一个重要性质。因此，近似不能帮助减少所需的ABP宽度。福布斯提到，当从单一（源，汇）ABP到追踪ABP时，这一结果可能会打破。我们证明这是正确的。此外，我们研究了交换单调集，证明了一个类似于Nisan的结果，但涉及解析闭包。我们在这里观察到相同的行为：ABP宽度复杂度最多为k的多项式集合对于单（源，汇）ABP是封闭的，而对于迹ABP则不是封闭的。证明揭示了一个有趣的连接切空间和向量空间的流动ABP。我们关闭额外的观察VQP和封闭的VNP，使我们能够建立两个类之间的分离。
Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most k is Zariski-closed, an important property in geometric complexity theory. It follows that approximations cannot help to reduce the required ABP width. It was mentioned by Forbes that this result would probably break when going from single-(source,sink) ABPs to trace ABPs. We prove that this is correct. Moreover, we study the commutative monotone setting and prove a result similar to Nisan, but concerning the analytic closure. We observe the same behavior here: The set of polynomials with ABP width complexity at most k is closed for single-(source,sink) ABPs and not closed for trace ABPs. The proofs reveal an intriguing connection between tangent spaces and the vector space of flows on the ABP. We close with additional observations on VQP and the closure of VNP which allows us to establish a separation between the two classes.