Item

Abstract

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.