×

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\).

MSC:

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
PDFBibTeX XMLCite
Full Text: DOI

References:

[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).; 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).; 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 \(P_2\), Matematicheskie voprosy kibernetiky 4 (Moscow, Nauka, 1992) 139-177 (in Russian).; V.A. Stetsenko, On almost bad bases in \(P_2\), 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).; 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.