A Boolean function requiring 3n network size (Q794625): Difference between revisions

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.