×

zbMATH — the first resource for mathematics

On a method for obtaining lower bounds for the complexity of individual monotone functions. (English. Russian original) Zbl 0616.94019
Sov. Math., Dokl. 31, 530-534 (1985); translation from Dokl. Akad. Nauk SSSR 282, 1033-1037 (1985).
It is shown that the lower bound for the complexity of minimal size monotone Boolean circuits reaches \(2^{n^{1/8-o(1)}}\).
Reviewer: A.Michalski

MSC:
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite