论文标题
置换产品的对称公式
Symmetric Formulas for Products of Permutations
论文作者
论文摘要
我们研究单词问题的公式复杂性$ \ MATHSF {word} _ {s_n，k}：\ {0,1 \}^{kn^2} \ to \ {0,1 \} $：给定$ n $ -n $ -by-by- $ n $ n $ - $ n $ n $ n $ n $ n $ permices $ _1，\ $ mm_1，\ dots $ $ $ $（MATR） $ M_1 \ CDOTS M_K $。此功能的一个重要功能是，它在$ s_n^{k-1} $的作用下是\ [ （π_1，\ dots，π_{k-1}）（m_1，\ dots，m_k）= （m_1π_1^{ - 1}，π_1M_2π_2^{ - 1}，\ dots，π_{k-2} m_ {k-1}π_{k-1}^k-1}^{ - 1}，π_{k-1} m_k）。 \]这种对称性也以最小的无限型粉丝$ \ {\ Mathsf {and}，\ Mathsf {或}，\ Mathsf {not} $公式 - 用于$ \ Mathsf {Wordsf {Word} _ {s_n，k} $ size size size size size size size size size（a）， 在本文中，我们证明了一个匹配的$ n^{ω（\ log k）} $下限$ s_n^{k-1} $ - 不变公式计算$ \ mathsf {word} _ {s_n，k} $。该结果的动机是因为不受限制的（不变）公式类似的下限将分开复杂性类别$ \ MATHSF {NC}^1 $和$ \ MATHSF {logSpace} $。 我们更一般的主要定理给出了几乎紧密的$ n^{d（k^{1/d} -1）} $下限，$ g^{k-1} $ - 不变的depth- $ d $ $ \ \ \ {\ mathsf {maj maj}对于任何有限的简单组$ g $，其最小置换表示为〜$ n $的任何有限的简单组$ g $，$ \ mathsf {word} _ {g，k} $。我们还对$ g^{k-1} $ - 不变的深度 - $ d $ \ \ {\ Mathsf {and}，\ Mathsf {or}，\ Mathsf {not} \} $ - $ G $是$ G $是Abelian组的公式大小。
We study the formula complexity of the word problem $\mathsf{Word}_{S_n,k} : \{0,1\}^{kn^2} \to \{0,1\}$: given $n$-by-$n$ permutation matrices $M_1,\dots,M_k$, compute the $(1,1)$-entry of the matrix product $M_1\cdots M_k$. An important feature of this function is that it is invariant under action of $S_n^{k-1}$ given by \[ (π_1,\dots,π_{k-1})(M_1,\dots,M_k) = (M_1π_1^{-1},π_1M_2π_2^{-1},\dots,π_{k-2}M_{k-1}π_{k-1}^{-1},π_{k-1}M_k). \] This symmetry is also exhibited in the smallest known unbounded fan-in $\{\mathsf{AND},\mathsf{OR},\mathsf{NOT}\}$-formulas for $\mathsf{Word}_{S_n,k}$, which have size $n^{O(\log k)}$. In this paper we prove a matching $n^{Ω(\log k)}$ lower bound for $S_n^{k-1}$-invariant formulas computing $\mathsf{Word}_{S_n,k}$. This result is motivated by the fact that a similar lower bound for unrestricted (non-invariant) formulas would separate complexity classes $\mathsf{NC}^1$ and $\mathsf{Logspace}$. Our more general main theorem gives a nearly tight $n^{d(k^{1/d}-1)}$ lower bound on the $G^{k-1}$-invariant depth-$d$ $\{\mathsf{MAJ},\mathsf{AND},\mathsf{OR},\mathsf{NOT}\}$-formula size of $\mathsf{Word}_{G,k}$ for any finite simple group $G$ whose minimum permutation representation has degree~$n$. We also give nearly tight lower bounds on the $G^{k-1}$-invariant depth-$d$ $\{\mathsf{AND},\mathsf{OR},\mathsf{NOT}\}$-formula size in the case where $G$ is an abelian group.
