分界分离：近似深度3电路的指数间隙扇入层次定理

《Journal of the ACM》：Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits

　　

摘要AI 摘要

要查看此 AI 生成的摘要，您必须拥有高级访问权限。

了解更多登录

摘要

摘要

Mulmuley 和 Sohoni（2001）提出了一个雄心勃勃的项目，称为几何复杂性理论（GCT），旨在利用代数几何和表示论来证明 P ≠ NP 及相关猜想。逐步地，GCT 在复杂性理论中引入了新的结构和问题。GCT 试图通过定义边界类来捕捉一种代数/几何意义上的"逼近"概念。令人惊讶的是，（Kumar ToCT'20）证明了顶扇入为 2 的深度为 3 的电路的边界的普遍计算能力（$\overline{({\mathrm{\Sigma }}^{[2]}\mathrm{\Pi }\mathrm{\Sigma }}$），这与其经典模型形成鲜明对比。最近，（Dutta, Dwivedi, Saxena, FOCS'21）通过证明有界顶扇入的边界深度为 3 的电路（$\overline{{\mathrm{\Sigma }}^{[k]}\mathrm{\Pi }\mathrm{\Sigma }}$，其中 k 为常数）可由多项式大小的代数分支程序（ABP）计算，从而给出了一个上界。关于在 ABP 类与$\overline{{\mathrm{\Sigma }}^{[k]}\mathrm{\Pi }\mathrm{\Sigma }}$之间证明指数级分离的问题仍悬而未决。

在本文中，我们证明了任意两个相邻的边界类$\overline{{\mathrm{\Sigma }}^{[k]}\mathrm{\Pi }\mathrm{\Sigma }}$和$\overline{{\mathrm{\Sigma }}^{[k+1]}\mathrm{\Pi }\mathrm{\Sigma }}$之间存在强指数级分离，从而建立了常数顶扇入的边界深度为 3 的电路的最优层级结构。用 GCT 的语言来说，我们证明了 ${\mathbb{F}}^{n+1}$的 Chow 簇的填充-k-次割簇的指数级层级结构。这正面回答了〔Dutta, Dwivedi, Saxena FOCS'21 的开放问题 2〕以及〔Landsberg, Annal.Ferrara'15 的问题 8.10（取常数 r）〕。

AI 摘要

AI 生成的摘要（实验性）

此摘要由自动化工具生成，未经文章作者撰写或审阅。提供此摘要是为了支持文献发现，帮助读者评估相关性，并协助相邻研究领域的读者理解该工作。它旨在补充作者提供的摘要，后者仍然是论文的主要摘要。全文仍为权威的正式版本。点击此处了解更多。

点击此处对此摘要的准确性、清晰度和实用性发表评论。这样做将有助于改进和生成未来版本。

要查看此 AI 生成的通俗摘要，您必须拥有高级访问权限。