{"id":"arxiv/2610.08198","url":"https://arxiv.org/abs/2610.08198","tags":["math.GR","cs.LO"],"score":0,"title":"Testing epimorphism onto the bicyclic monoid is $\\mathsf{NP}$-complete","domain":"math.GR","source":"arxiv","authors":["Luka Carroll","Murray Elder"],"reviews":0,"subject":"math.GR","summary":"We prove that deciding whether there is a surjective homomorphism from an arbitrary finitely presented inverse monoid onto the bicyclic monoid is $\\mathsf{NP}$-complete. As part of the proof, we show that an extension of existential Presburger arithmetic which involves greatest common divisors on $n$ arguments is in $\\mathsf{NP}$, extending a recent result of Défossez, Haase, Mansutti, and Pérez (SODA 2024).","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-06","reactions":{}}