On Defining Integers And Proving Arithmetic Circuit Lower Bounds
On Defining Integers And Proving Arithmetic Circuit Lower Bounds
复制标题
关于整数的定义和算术电路下界的证明
DOI：
--
复制
发表时间：
2009
影响因子：
1.4
通讯作者：
Peter Bürgisser
中科院分区：
文献类型：
--
作者：
Peter Bürgisser
摘要：设 τ(n) 表示足以从常数 1 构造整数 n 的算术运算的最小数量。我们证明，如果存在 n 大小多项式的算术电路用于计算 n 乘以 n 矩阵的常量，则 τ(n!) 多项式有界于 log n。在相同的永久假设下，我们得出 Pochhammer–Wilkinson 多项式 $$Pi^{n}_{k=1}(X - k)$$ 和泰勒近似 $$Sigma^{n}_{k=0}frac{1}{k!}X^{k}$$ 和 exp 和 log 的 $$Sigma^{n}_{k=1}frac{1}{k}X^{k}$$ 分别可以通过 log n 大小多项式的算术电路（允许除法）计算。这将代数复杂性中迄今为止不相关的几个猜想联系起来。
Abstract.Let τ(n) denote the minimum number of arithmetic operations sufficient to build the integer n from the constant 1. We prove that if there are arithmetic circuits of size polynomial in n for computing the permanent of n by n matrices, then τ(n!) is polynomially bounded in log n. Under the same assumption on the permanent, we conclude that the Pochhammer–Wilkinson polynomials $$Pi^{n}_{k=1}(X - k)$$ and the Taylor approximations $$Sigma^{n}_{k=0}frac{1}{k!}X^{k}$$ and $$Sigma^{n}_{k=1}frac{1}{k}X^{k}$$ of exp and log, respectively, can be computed by arithmetic circuits of size polynomial in log n (allowing divisions). This connects several so far unrelated conjectures in algebraic complexity.