Testing epimorphism onto the bicyclic monoid is $\mathsf{NP}$-complete

Luka Carroll, Murray Elder

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…