PreprintCC BY 4.0arXiv
Testing epimorphism onto the bicyclic monoid is NP-complete
Abstract
We prove that deciding whether there is a surjective homomorphism from an arbitrary finitely presented inverse monoid onto the bicyclic monoid is 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 NP, extending a recent result of Défossez, Haase, Mansutti, and Pérez (SODA 2024).
Related
BibTeX
@misc{carroll2026testing,
title = {{Testing epimorphism onto the bicyclic monoid is $\mathsfNP$-complete}},
author = {Luka Carroll and Murray Elder},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08198},
eprint = {2610.08198},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08198},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Testing epimorphism onto the bicyclic monoid is NP-complete
AU - Luka Carroll
AU - Murray Elder
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.08198
UR - https://arxiv.org/abs/2610.08198
AB - We prove that deciding whether there is a surjective homomorphism from an arbitrary finitely presented inverse monoid onto the bicyclic monoid is 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 NP, extending a recent result of Défossez, Haase, Mansutti, and Pérez (SODA 2024).
ER -