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

CREATORMurray Elder, Jerry Shen, Armin Weiß
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE151 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-05283

Browse the full library · About the Tower of Babel