Abstract:
The paper is focused on decomposition of Boolean functions on the form $f_1\circ\ldots\circ f_m$, where $\circ$ is a commutative associative operation and $f_1,\ldots,f_m$ are Boolean functions with fewer arguments. For each commutative associative operation, we define necessary and sufficient conditions for the absence of such a decomposition and find the related complexity class.