A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions | Zendy

Wolfgang J. Paul | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions

Author(s) -

Wolfgang J. Paul

Publication year - 1977

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/0206030

Subject(s) - boolean function , mathematics , boolean circuit , sequence (biology) , combinatorics , circuit complexity , upper and lower bounds , discrete mathematics , computational complexity theory , omega , time complexity , complexity index , binary logarithm , boolean expression , combinational logic , algorithm , logic gate , electronic circuit , mathematical analysis , electrical engineering , engineering , genetics , physics , quantum mechanics , biology

Consider the combinational complexity $L(f)$ of Boolean functions over the basis $\Omega = \{ f|f:\{ 0,1\} ^2 \to \{ 0,1\} \} $. A new method for proving linear lower bounds of size $2n$ is presented. Combining it with methods presented in Savage [13, (1974)] and Schnorr [18, (1974)], we establish for a special sequence of functions $f_n :\{ 0,1\} ^{n + 2\log (n) + 1} \to \{ 0,1\} :2.5n \leqq L(f) \leqq 6n$. Also a trade-off result between circuit complexity and formula size is derived.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research