no. 5 · Friday 30 October 2026
On the complexity of epimorphism testing with virtually abelian targets
Abstract
Friedl and Löh (2021, Confl. Math.) prove that testing whether or not there is an epimorphism from a finitely presented group to the direct product of an abelian and a finite group, or to a virtually cyclic group, is decidable. Here we prove that these problems are $\mathsf{NP}$-complete. In addition, we show that testing epimorphism is $\mathsf{NP}$-complete when the target is is the semi-direct product of a finitely generated free-abelian group and a finite group which factors through $\{\pm\text{Id}\}$, thus extending the class of virtually abelian target groups for which decidability of epimorphism is known.
- comments
- 27 pages. Sections 7-9 of previous version of this paper split into a separate article arxiv:TBA
- fields
- Group Theory