On the depth complexity of formulas
On the depth complexity of formulas
复制标题
论公式的深度复杂度
DOI：
10.1007/bf01744302
复制
发表时间：
1979
期刊：
影响因子：
--
通讯作者：
M. Snir
中科院分区：
文献类型：
--
作者：
E. Shamir;M. Snir
通过等价保持变换最小化公式深度的问题在一般代数环境中被形式化。对于特定的代数系统 Σ0 ，开发了动态规划性质的特定方法来证明深度的下界。 Σ0 的此类下界自动意味着以下系统的结果相同：(i) 仅使用加法和乘法的算术计算，以及 (ii) 使用并集和串联对有限语言进行的计算。获得的具体下界是 (i) 永久的深度 2n−o(n)，(ii) 对称多项式的深度 (0.25+o(1))log2n 和 (iii) 公式 sizen 问题的深度 1.16logn。
The problem of minimizing the depth of formulas by equivalence preserving transformations is formalized in a general algebraic setting. For a particular algebraic system ∑0 specific methods of a dynamic programming nature are developed for proving lower bounds on depth. Such lower bounds for ∑0 automatically imply the same results for the systems of (i) arithmetic computations with addition and multiplication only, and (ii) computations over finite languages using union and concatenation. The specific lower bounds obtained are (i) depth 2n−o(n) for the permanent, (ii) depth (0.25+o(1))log2n for the symmetric polynomials and (iii) depth 1.16logn for a problem of formula sizen.