The complexity hierarchy of Boolean bases

MaRDI QIDQ5960222zbMATH OpenFDO

Authors D. Yu. Cherukhin

Publication date 14 April 2002

Published in Moscow University Mathematics Bulletin (Search for Journal in Brave)

zbMATH Keywords

Boolean basescomposite hierarchy

Mathematics Subject Classification ID

Boolean functions (06E30)

Review text

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.

Recommendations

• On the comparison of Boolean bases
• scientific article; zbMATH DE number 4072877
• On some series of bases for the set of Boolean functions
• On almost bad Boolean bases
• scientific article; zbMATH DE number 4049556

Cited in

(11)

• An improved complexity hierarchy on the depth of Boolean functions
• On almost bad Boolean bases
• On the comparison of Boolean bases
• scientific article; zbMATH DE number 4045650 (Why is no real title available?)
• scientific article; zbMATH DE number 4049556 (Why is no real title available?)
• scientific article; zbMATH DE number 4104874 (Why is no real title available?)
• On the premaximal Boolean bases
• Boolean complexity classes vs. their arithmetic analogs
• An algorithmic criterion for the comparison of Boolean bases.
• On an infinite sequence of improving Boolean bases
• On the computational power of Boolean decision lists

This page was built for publication: The complexity hierarchy of Boolean bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5960222)