Circuit Complexity and Multiplicative Complexity of Boolean Functions

被引：0
|
作者：
Kojevnikov, Arist [1 ]
Kulikov, Alexander S. [1 ]
机构：
[1] VA Steklov Math Inst, St Petersburg Dept, Moscow 117333, Russia
来源：
PROGRAMS, PROOFS, PROCESSES | 2010年 / 6158卷
关键词：
COMBINATIONAL COMPLEXITY; BOUNDS;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this note, we use lower bounds on Boolean multiplicative complexity to prove lower bounds on Boolean circuit complexity. We give a very simple proof of a 7n/3 - c lower bound on the circuit complexity of a large class of functions representable by high degree polynomials over GF(2). The key idea of the proof is a circuit complexity measure assigning different weights to XOR and AND gates.
引用
收藏
页码：239 / 245
页数：7
相关论文
共 50 条
12345