Open Research Index

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

Luka Carroll, Murray Elder

arXivarxiv/2610.08198Oct 6, 2026math.GRscore 0

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).

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2610.08198
curl -X POST /api/v1/records/arxiv/2610.08198/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.08198/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'