zbMATH — the first resource for mathematics

A Boolean function requiring 3n network size. (English) Zbl 0539.94036
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. 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.

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Blum, N., A 2.75n-lower bound on the network complexity of Boolean functions, ()
[2] Paul, W.J., A 2.5n-lower bound on the combinational complexity of Boolean functions, SIAM J. comput., 6, 427-443, (1977) · Zbl 0358.68081
[3] Schnorr, C.P., Zwei lineare untere schranken für die komplexität boolescher funktionen, Computing, 13, 155-171, (1974) · Zbl 0313.68033
[4] Schnorr, C.P., A 3n-lower bound on the network complexity of Boolean functions, Theoret. comput. sci., 10, 83-92, (1980) · Zbl 0438.68012
[5] Stockmeyer, L.J., On the combinational complexity of certain symmetric Boolean functions, Math. systems theory, 10, 323-336, (1977) · Zbl 0369.94016
[6] I. Wegener, Private communication, 1981.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.