The complexity hierarchy of Boolean bases (Q5960222)

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 [\textit{B.~A.~Subbotovskaya}, Sov. Math. Dokl. 4, 478-481 (1963; Zbl 0154.25903); \textit{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.