# 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