On the complexity of epimorphism problems for finitely generated groups

Shen, Qing

On the complexity of epimorphism problems for finitely generated groups

Shen, Qing

Permalink

Publication Type:: Thesis
Issue Date:: 2025

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download thesisAdobe PDF (877.13 kB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Shen, Qing
dc.date.accessioned	2026-05-19T01:04:16Z
dc.date.available	2026-05-19T01:04:16Z
dc.date.issued	2025
dc.identifier.uri	http://hdl.handle.net/10453/195042
dc.description	University of Technology Sydney. Faculty of Science.	en_US.UTF-8
dc.description.abstract	The epimorphism problem for groups asks whether, given groups G and H, there exists a surjective homomorphism from G to H. It is related to the isomorphism problem but can be strictly harder; for example, it is undecidable for some nilpotent groups. Friedl and Löh (2021, Confl. Math.), building on Remeslennikov (1979, Sibirsk. Mat. Zh.), proved decidability for certain virtually abelian targets and conjectured undecidability in full generality. In this thesis we show that, for the target classes considered by Friedl and Löh, the epimorphism problem is NP-complete. We further enlarge the collection of virtually abelian groups for which the problem is both decidable and NP-complete, and develop an alternative approach based on associated integer matrix problems, proving two of these lie in P and linking a third to the general virtually abelian case. For fixed finite targets, we prove NP-completeness when H is a dihedral group of order not a power of 2. This complements a result of Kuperberg and Samperton (2018, Geom. Topol.), who established NP-completeness for non-abelian finite simple targets. Finally, we survey existing work to give, as far as currently known, an almost complete complexity classification for the epimorphism problem.	en_US.UTF-8
dc.format	Thesis (PhD)
dc.language.iso	en_US	en_US.UTF-8
dc.relation	https://opus.lib.uts.edu.au/bitstream/10453/195042/1/thesis.pdf
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	The author owns the copyright in this thesis including all reproduction and reuse rights for the work. The work may not be altered without the permission of the copyright owner. Attribution is essential when quoting or paraphrasing from this thesis.
dc.rights	© 2025 Qing (Jerry) Shen
dc.rights	au.edu.uts.lib/cph
dc.title	On the complexity of epimorphism problems for finitely generated groups	en_US.UTF-8
dc.type	Thesis
utslib.copyright.status	open_access	*

Abstract:

The epimorphism problem for groups asks whether, given groups G and H, there exists a surjective homomorphism from G to H. It is related to the isomorphism problem but can be strictly harder; for example, it is undecidable for some nilpotent groups. Friedl and Löh (2021, Confl. Math.), building on Remeslennikov (1979, Sibirsk. Mat. Zh.), proved decidability for certain virtually abelian targets and conjectured undecidability in full generality. In this thesis we show that, for the target classes considered by Friedl and Löh, the epimorphism problem is NP-complete. We further enlarge the collection of virtually abelian groups for which the problem is both decidable and NP-complete, and develop an alternative approach based on associated integer matrix problems, proving two of these lie in P and linking a third to the general virtually abelian case. For fixed finite targets, we prove NP-completeness when H is a dihedral group of order not a power of 2. This complements a result of Kuperberg and Samperton (2018, Geom. Topol.), who established NP-completeness for non-abelian finite simple targets. Finally, we survey existing work to give, as far as currently known, an almost complete complexity classification for the epimorphism problem.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/195042