a 2.5 n-lower bound on the combinational complexity of boolean functions
Consider the combinational complexity L(f) of Boolean functions over the basis &Ohgr; &equil; {f f:{0,1} 2 ? {0,1}}. A new Method for proving linear lower bounds of size 2n is presented. Combining it with methods presented in [12] and [15], we establish for a special sequence of functions f n :{0,1} n ? {0,1}: 2.5n ? L(f) &le 6n. Also a trade-off result between circuit complexity and formula size is derived.
lower bound combinational complexity method size sequence circuits