Boolean Functions, Invariance Groups, and Parallel Complexity
Peter Colte, Evangelos Kranakis · SIAM Journal on Computing · 1991
This paper studies the invariance groups ${\bf S}(f)$ of boolean functions $f \in {\bf B}_n $ (i.e., $f:\{ 0,1\} ^n \to \{ 0,1\} $) on n variables, i.e., the set of all permutations on n elements which leave f invariant. After building intuition by presenting several examples that suggest relations between algebraic properties of groups and computational complexity of languages, necessary and sufficient conditions are given via Pólya’s cycle index for an arbitrary finite permutation group to be of the form $S(f)$, for some $f \in {\bf B}_n $. It is shown that asymptotically “almost all” boolean functions have trivial invariance groups. For cyclic groups $G \leqq {\bf S}_n $ a logspace algorithm for determining whether the given group is of the form ${\bf S}(f)$, for some $f \in {\bf B}_n $ is given. The applicability of group theoretic techniques in the study of the parallel complexity of languages is demonstrated. For any language L let $L_n $ be the characteristic function of the set of all strings in L which have length exactly n and let ${\bf S}_n (L)$ be the invariance group of $L_n $. The index $| {{\bf S}_n :{\bf S}_n (L)} |$ are considered as a function of n and the class of languages whose index is polynomial in n is studied. Bochert’s lower bound on the index of primitive permutation groups is used together with the O’Nan-Scott theorem, a deep result in the classification of finite simple groups, in order to show that any language with polynomial index is in (nonuniform) ${\text{TC}}^0 $ and hence in (nonuniform) ${\text{NC}}^1 $. As a corollary, an extension is given of a result of Fagin–Klawe-Pippenger–Stockmeyer, giving necessary and sufficient conditions for a language with polynomial index to be computable by a constant depth polynomial size circuit family. As another corollary, it is shown that the problem of “weight-swapping” for a sequence of groups of polynomial index is in (nonuniform) ${\text{NC}}^1 $.