zbMATH — the first resource for mathematics

The complexity hierarchy of Boolean bases. (English. Russian original) Zbl 0987.06013
Mosc. Univ. Math. Bull. 55, No. 3, 32-34 (2000); translation from Vestn. Mosk. Univ., Ser. I 2000, No. 3, 48-50 (2000).
The paper deals with the investigation of the dependence of the complexity of formulas of Boolean functions on their functional basis. A partial order relation is used that was introduced in [B. A. Subbotovskaya, Sov. Math. Dokl. 4, 478-481 (1963; Zbl 0154.25903); V. A. Stetsenko, Mat. Vopr. Kibern. 4, 139-177 (1992; Zbl 0805.06015)]. The author proposes a criterion which allows to verify whether this partial order relation is satisfied for arbitrary bases.
06E30 Boolean functions
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)