版本更新 · v2arXiv:2501.05283
On the complexity of epimorphism testing with virtually abelian targets
Murray Elder, Jerry Shen, Armin Weiß
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.
尚无 AI 解读，展示原文摘要
math.GR · cs.CC