2025/02/10 by Larrauri, Alberto, Mottet, Antoine, Živný, Stanislav
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2502.06762
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.