Formula Complexity of a Linear Function in a $$k$$-ary Basis
Igor' Sergeevich Sergeev · Mathematical Notes · 2021
The Khrapchenko method of finding a lower bound for the complexity of binary formulas is extended to formulas in $$k$$ -ary bases. The resulting extension makes it possible to evaluate the complexity of linear Boolean functions and a majority function of $$n$$ variables when realized by formulas in the basis of all $$k$$ -ary monotone functions and negation as $$\Omega(n^{g(k)})$$ , where $$g (k)=1+\Theta(1/\ln k)$$ . For a linear function, the complexity bound in this form is unimprovable. For $$k=3$$ , the sharper lower bound $$\Omega(n^{1.53})$$ is proved.