Permutation group problems shown to have high computational complexity
Word Length and Diameter in Permutation Groups
Computational Complexity
Summary
This paper looks at how hard it is to figure out how many steps it takes to build every element of a certain mathematical group from given basic pieces. The authors show that deciding whether every element can be formed with a limited number of steps is very complicated to compute, falling into a high complexity class called PSPACE-complete. For a special kind of groups called 2-step nilpotent groups, the problem has slightly different complexity classifications. This kind of work helps us understand the limits of what computers can efficiently solve in group theory.
What this means in practice
- •For cryptography engineers: Recognize limits on efficient algorithms for manipulating group elements in cryptographic protocols relying on permutation groups.
- •For algorithm designers: Use complexity boundaries to avoid inefficient approaches for length and diameter problems in permutation group computations.
A theory result. No direct application yet.
Authors
Markus Lohrey, Alexander Thumm
Abstract
The input for the binary diameter problem consists of explicitly represented permutations generating a finite group $G$ and a binary-encoded nonnegative integer $k$. The question is whether every element of $G$ is a product of at most $k$ input generators. For the binary length problem, the input contains in addition a permutation $g \in G$ and it is asked whether $g$ is a product of at most $k$ input generators. We prove that the binary diameter problem is PSPACE-complete. When restricted to $2$-step nilpotent groups, the binary diameter problem is shown to be complete for $\mathsf{Π_2^P}$, whereas the binary length problem is shown to be NP-complete. Without the restriction to $2$-step nilpotent groups, the binary length problem is PSPACE-complete by a result of Jerrum.