Easy lower bound for a strange computational model

被引：0

作者：

Smolensky, R

机构：

来源：

COMPUTATIONAL COMPLEXITY | 1997年 / 6卷 / 03期

关键词：

circuits; lower bounds; algebraic complexity;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The paper gives a new proof of the well-known lower bound Omega(n log n) for the algebraic complexity of the function x(1)(n) + x(2)(n) + ... + x(n)(n) (if the characteristic of the ground field does not divide n). As a tool, the proof uses a computational model that counts only duplicators.

引用

页码：213 / 216

页数：4