Lower estimates of circuits complexity in the basis of antichain functions / O. V. Podol'skaya. //Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2013. № 2. P. 17-23 [Moscow Univ. Math. Bulletin. Vol. 68, N 2, 2013.].
The antichain function is a characteristic function of an antichain in the Boolean cube. The set of antichain functions is an infinite complete basis. We study the computational complexity of Boolean functions over an antichain functional basis. In this paper we prove an asymptotic lower bound of order √n on the computational complexity of the linear function, the majority function, and almost all Boolean functions of n variables.
Key words: antichain function, Boolean circuits, linear function, majority function.