A Boolean function requiring 3n network size

From MaRDI portal





One of the most difficult problems in complexity theory is proving a nonlinear lower bound for the network complexity of an explicit Boolean function. Although it is well known by a counting argument that relative to the full basis most Boolean functions need exponentially many operations, only linear lower bounds with small constant factor are known for explicit Boolean functions. \textit{W. J. Paul} [SIAM J. Comput. 6, 427- 443 (1977; Zbl 0358.68081)] has proved a 2.5n-lower bound over the complete basis over all binary functions for an explicit Boolean function. We modify the definition of Paul's function slightly and prove a 3n-lower bound for the network complexity of that function. This is the best known lower bound over the complete basis of all binary Boolean functions.




Cited in
(53)








This page was built for publication: A Boolean function requiring 3n network size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q794625)