BOOLEAN FUNCTIONS, INVARIANCE-GROUPS, AND PARALLEL COMPLEXITY

作     者：CLOTE, P KRANAKIS, E 

作者机构：UNIV PARIS 07 EQUIPE LOG MATH CNRS UA 753 F-75221 PARIS 05 FRANCE CTR WISKUNDE & INFORMAT 1009 AB AMSTERDAM NETHERLANDS 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1991年第20卷第3期

页      面：553-590页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：ABELIAN GROUP BOOLEAN FUNCTION CIRCUIT CLASSIFICATION THEORY CYCLIC GROUPS DIHEDRAL GROUPS HYPEROCATAHEDRAL-GROUPS INDEX OF A GROUP INVARIANCE GROUP OF BOOLEAN FUNCTION NC PARALLEL COMPLEXITY PERMUTATION GROUP POLYA CYCLE INDEX PUMPING LEMMA REPRESENTABLE GROUP REGULAR LANGUAGE SYMMETRICAL BOOLEAN FUNCTION WREATH PRODUCT 

摘      要：This paper studies the invariance groups S(f) of boolean functions f member-of B(n) (i.e., f:{0,1}n -- {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 Polya s cycle index for an arbitrary finite permutation group to be of the form S(f), for some f member-of B(n). It is shown that asymptotically almost all boolean functions have trivial invariance groups. For cyclic groups G less-than-or-equal-to S(n) a logspace algorithm for determining whether the given group is of the form S(f), for some f member-of 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 S(n)(L) be the invariance group of L(n). The index \S(n):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) TC0 and hence in (nonuniform) NC1. 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) NC1.