zbMATH — the first resource for mathematics

On the complexity of realization of the linear function by formulas over finite Boolean bases. (English. Russian original) Zbl 0965.03075
Discrete Math. Appl. 10, No. 2, 147-157 (2000); translation from Diskretn. Mat. 12, No. 1, 135-144 (2000).
Summary: We completely describe the set of bases over which the complexity of realization of the function \(x_1\oplus\cdots\oplus x_n\) is of order \(n\). For all bases not belonging to this set, we obtain the lower bound for the complexity of realization of the function \(x_1\oplus\cdots\oplus x_n\), which is of the form \(n^c\), where \(c>1\) and \(c\) does not depend on \(n\). Basing on this bound for complexity, we give a simpler proof of the existence of an infinite (descending) sequence of Boolean bases.
03G05 Logical aspects of Boolean algebras
03D15 Complexity of computation (including implicit computational complexity)
06E30 Boolean functions
03B05 Classical propositional logic
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI