On the complexity of epimorphism testing with virtually abelian targets
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915101981802496 |
|---|---|
| author | Elder, Murray Shen, Jerry Weiß, Armin |
| author_facet | Elder, Murray Shen, Jerry Weiß, Armin |
| contents | Friedl and Löh (2021, Confl. Math.) prove that testing whether or not there is an epimorphism from a finitely presented group to a virtually cyclic group, or to the direct product of an abelian and a finite group, is decidable. Here we prove that these problems are $\mathsf{NP}$-complete. We also show that testing epimorphism is $\mathsf{NP}$-complete when the target is a restricted type of semi-direct product of a finitely generated free abelian group and a finite group, thus extending the class of virtually abelian target groups for which decidability of epimorphism is known. Lastly, we consider epimorphism onto a fixed finite group. We show the problem is $\mathsf{NP}$-complete when the target is a dihedral groups of order that is not a power of 2, complementing the work on Kuperberg and Samperton (2018, Geom. Topol.) who showed the same result when the target is non-abelian finite simple. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_05283 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the complexity of epimorphism testing with virtually abelian targets Elder, Murray Shen, Jerry Weiß, Armin Group Theory Computational Complexity 20F10, 20F65, 68Q17 Friedl and Löh (2021, Confl. Math.) prove that testing whether or not there is an epimorphism from a finitely presented group to a virtually cyclic group, or to the direct product of an abelian and a finite group, is decidable. Here we prove that these problems are $\mathsf{NP}$-complete. We also show that testing epimorphism is $\mathsf{NP}$-complete when the target is a restricted type of semi-direct product of a finitely generated free abelian group and a finite group, thus extending the class of virtually abelian target groups for which decidability of epimorphism is known. Lastly, we consider epimorphism onto a fixed finite group. We show the problem is $\mathsf{NP}$-complete when the target is a dihedral groups of order that is not a power of 2, complementing the work on Kuperberg and Samperton (2018, Geom. Topol.) who showed the same result when the target is non-abelian finite simple. |
| title | On the complexity of epimorphism testing with virtually abelian targets |
| topic | Group Theory Computational Complexity 20F10, 20F65, 68Q17 |
| url | https://arxiv.org/abs/2501.05283 |