zbMATH — the first resource for mathematics

On an infinite sequence of improving Boolean bases. (English. Russian original) Zbl 0991.06009
Discrete Appl. Math. 114, No. 1-3, 95-108 (2001); translation from Diskretn. Anal. Issled. Oper., Ser. 1 4, No. 4, 79-95 (1997).
Summary: We consider complexity of formulas for Boolean functions in finite complete bases. It is shown that, with regard to complexity, the basis of all \((k+1)\)-ary functions is essentially better than the basis of all \(k\)-ary functions for all \(k\geq 2\).

06E30 Boolean functions
03D15 Complexity of computation (including implicit computational complexity)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] O.B. Lupanov, On complexity of realization of functions of algebra of logic by formulas, Problemy kibernetiki 3 (Moscow, Fizmatgiz, 1960) 61-80 (in Russian).
[2] B.A. Muchnik, Complexity bound for realization of linear function in some bases, Kibernetika 4 (1970) 29-38 (in Russian). · Zbl 0285.68024
[3] V.A. Stetsenko, On almost bad bases in P2, Matematicheskie voprosy kibernetiky 4 (Moscow, Nauka, 1992) 139-177 (in Russian). · Zbl 0805.06015
[4] B.A. Subbotovskaya, On comparison of bases under realization of functions of Boolean algebra by formulas, Dokl. AN SSSR 149(4) (1963) 784-787 (in Russian). · Zbl 0154.25903
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.