## A lower bound on complexity of branching programs.(English)Zbl 0572.68033

Mathematical foundations of computer science, Proc. 11th Symp., Praha/Czech. 1984, Lect. Notes Comput. Sci. 176, 480-489 (1984).
[For the entire collection see Zbl 0544.00022.]
The bound $$\Omega$$ (n log log n (log log log n)$${}^{-1})$$ is proved to the size of branching programs which realize some symmetric functions.

### MSC:

 68Q25 Analysis of algorithms and problem complexity 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)

Zbl 0544.00022