Word Length and Diameter in Permutation Groups
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}$,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.26307
curl -X POST /api/v1/records/arxiv/2609.26307/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.26307/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'