永久式的边界行列式复杂度的三次下界
A cubic lower bound for border determinantal complexity of the permanent
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
该稿件研究m×m永久式的复边界行列式复杂度，作者声称证明了Ω(m³)的下界，且允许任意仿射线性行列式表示以及逐系数极限。摘要还表示，这一结果同时给出精确行列式复杂度的三次下界，以及仿射线性代数分支程序中顶点数和边数的三次下界，包括在固定顶点或边预算下的逐系数极限情形。研究意义在于为永久式的行列式型复杂度提供更强的下界工具，但结论仍属作者声称，尚待独立审查。
- 作者声称m×m永久式的复边界行列式复杂度为Ω(m³)。
- 结果允许任意仿射线性行列式表示及逐系数极限。
- 同时给出精确行列式复杂度与仿射线性代数分支程序规模的三次下界。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We prove that the complex border determinantal complexity of the $`m\times m`$ permanent is $`\Omega(m^3)`$, allowing arbitrary affine-linear determinant representations and coefficientwise limits. It also gives cubic lower bounds for exact determinantal complexity and for the numbers of vertices and edges in affine-linear algebraic branching programs, including coefficientwise limits with a fixed vertex or edge budget.
用户标记：未标记
固定编号：620a0d74c214d423
原文来源