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.


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


Zbl 0544.00022