Equations over Finite Monoids with Infinite Promises
Provides a more general complexity classification for promise constraint satisfaction problems over monoids, benefiting researchers in computational complexity and algebra.
This paper extends the complexity classification of solving equations over finite monoids with promises to arbitrary relations and finitely generated monoids, establishing a dichotomy theorem.
Larrauri and Živný [ICALP'25/ACM ToCL'24] recently established a complete complexity classification of the problem of solving a system of equations over a monoid $N$ assuming that a solution exists over a monoid $M$, where both monoids are finite and $M$ admits a homomorphism to $N$. Using the algebraic approach to promise constraint satisfaction problems, we extend their complexity classification in two directions: we obtain a complexity dichotomy in the case where arbitrary relations are added to the monoids, and we moreover allow the monoid $M$ to be finitely generated.