论文标题
有限群体的会员问题
Membership Problems in Finite Groups
论文作者
论文摘要
我们表明，置换组的子集总和问题，背包问题和合理子集成员资格问题是NP完整的。关于背包问题，我们为每个固定的$ n \ geq 3 $获得NP完整性，其中$ n $是背包方程中的排列数。换句话说：三个循环置换组的产品的成员资格是NP完整的。这是luks的结果，该结果指出了三个Abelian置换组产品的成员问题的NP完整性。我们还考虑了置换组中的无上下文成员资格问题，并证明它是PSPACE份数的，但对于限制的无上下文语法类别的NP组件，无循环衍生树必须具有恒定的Horton-strahler编号。我们的上限适用于黑匣子组。置换组中无上下文成员问题的结果为DFA和单个无上下文语法提供了各种交点的非空置问题的新复杂性界限。
We show that the subset sum problem, the knapsack problem and the rational subset membership problem for permutation groups are NP-complete. Concerning the knapsack problem we obtain NP-completeness for every fixed $n \geq 3$, where $n$ is the number of permutations in the knapsack equation. In other words: membership in products of three cyclic permutation groups is NP-complete. This sharpens a result of Luks, which states NP-completeness of the membership problem for products of three abelian permutation groups. We also consider the context-free membership problem in permutation groups and prove that it is PSPACE-complete but NP-complete for a restricted class of context-free grammars where acyclic derivation trees must have constant Horton-Strahler number. Our upper bounds hold for black box groups. The results for context-free membership problems in permutation groups yield new complexity bounds for various intersection non-emptiness problems for DFAs and a single context-free grammar.
