A NONLINEAR LOWER-BOUND ON THE PRACTICAL COMBINATIONAL COMPLEXITY

An infinite sequence F = {f(n)}(infinity)(n=1), of one-output Boolean functions with the following two properties is constructed: (1) f(n) c an be computed by a Boolean circuit with O(n) gates. (2) For any posit ive, nondecreasing, and unbounded function h: N --> R, each Boolean ci rcuit having an m/h(m) separator requires a nonlinear number Omega(nh( n)) of gates to compute f(n) (e.g., each planar Boolean circuit requir es Omega(n(2)) gates to compute f(n)). Thus, one can say that f(n) has linear combinational complexity and a nonlinear practical combination al complexity because the constant-degree parallel architectures used in practice have separators in O(m/log(2)m),