×

zbMATH — the first resource for mathematics

Realization of linear functions by formulas in various bases. (English. Russian original) Zbl 1028.94044
Mosc. Univ. Math. Bull. 56, No. 6, 14-18 (2001); translation from Vestn. Mosk. Univ., Ser. I 2001, No. 6, 15-19 (2001).
The author studies the complexity of the realization of a linear Boolean function \(x_1\oplus\dots\oplus x_n\) by formulas in various bases. The author divides all the bases into three types: in the bases of the first type, the order of the complexity of realization of a linear function equals \(n^2\); in the bases of the second type, the order of complexity is not smaller than \(n^\beta\) and not larger than \(n^\gamma\), where \(1<\beta<\gamma<2\) (the constants \(\beta\) and \(\gamma\) are calculated with respect to the basis); and in the bases of the third type, the order of complexity equals \(n\).
MSC:
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q25 Analysis of algorithms and problem complexity
68W40 Analysis of algorithms
PDF BibTeX XML Cite