• A
• A
• A
• ABC
• ABC
• ABC
• А
• А
• А
• А
• А
Regular version of the site
The antichain function is a characteristic function of antichain on the Boolean cube. The set of antichain functions is an infinite complete basis. We study computational complexity of Boolean functions over antichain functional basis. In this paper we prove $\sqrt{n}$ asymptotic lower bound on the computational complexity of the linear function, the majority function and almost all Boolean function of $n$ variables.