A Boolean function requiring 3n network size (Q794625)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A Boolean function requiring 3n network size |
scientific article |
Statements
A Boolean function requiring 3n network size (English)
0 references
1984
0 references
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.
0 references
lower bound
0 references
network complexity
0 references
Boolean function
0 references