On the complexity of epimorphism testing with virtually abelian targets
Murray Elder, Jerry Shen, Armin Weiß · 2025
Read On the complexity of epimorphism testing with virtually abelian targets by Murray Elder, Jerry Shen, Armin Weiß (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-05283.txt.
Description
Murray Elder, Jerry Shen, and Armin Weiß settled the difficulty of an algebraic decision problem in 2025. The problem asks whether one finitely presented group maps onto a given target group, preserving structure, a question called epimorphism testing. Earlier work by Friedl and Löh had shown the question is decidable when the target is built from an abelian group and a finite group, or is nearly cyclic.
Decidable, however, does not mean easy. The authors prove these testing problems are NP-complete, the standard class of hard but checkable problems. They also prove NP-completeness for a wider family of targets, semi-direct products of a free-abelian group with a finite group that acts through a sign choice. The result extends the range of nearly abelian targets where the complexity of epimorphism testing is now pinned down.
Catalog record
| CREATOR | Murray Elder, Jerry Shen, Armin Weiß |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 151 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-05283