Solving promise equations over monoids and groups
<|reference_start|>Solving promise equations over monoids and groups: We give a complete complexity classification for the problem of finding a solution to a given system of equations over a fixed finite monoid, given that a solution over a more restricted monoid exists. As a corollary, we obtain a complexity classification for the same problem over groups.<|reference_end|>
@article{larrauri2024solving,
    title={Solving promise equations over monoids and groups},
    author={Alberto Larrauri and Stanislav v{Z}ivn'y},
    journal={arXiv preprint arXiv:2402.08434},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.08434},
    primaryClass={cs.CC cs.LO}
}