A Selection of Lower Bounds for Arithmetic Circuits
A Selection of Lower Bounds for Arithmetic Circuits
复制标题
算术电路下界的选择
DOI：
10.1007/978-3-319-05446-9_5
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Ramprasad Saptharishi
中科院分区：
文献类型：
--
作者：
N. Kayal;Ramprasad Saptharishi
多项式起源于有关几何和方程组解的经典数学研究。它们在代数、数论和几何中的许多经典结果中占有重要地位，例如伽罗瓦和阿贝尔通过五次根式解决了可解性，拉格朗日定理将每个自然数表示为四个平方和，以及三等分角度的不可能性（使用尺子和圆规）。在现代，计算机科学家开始研究哪些函数可以（有效）计算。多项式是一类自然函数，自然会导致以下问题：
Polynomials originated in classical mathematical studies concerning geometry and solutions to systems of equations. They feature in many classical results in algebra, number theory and geometry e.g. in Galois and Abel’s resolution of the solvability via radicals of a quintic, Lagrange’s theorem on expressing every natural number as a sum of four squares and the impossibility of trisecting an angle (using ruler and compass). In modern times, computer scientists began to investigate as to what functions can be (efficiently) computed. Polynomials being a natural class of functions, one is naturally lead to the following question: