Equations over Finite Monoids with Infinite Promises

Alberto Larrauri; Antoine Mottet; Stanislav \v{Z}ivn\'y

arxiv: 2502.06762 · v4 · submitted 2025-02-10 · 💻 cs.CC

Equations over Finite Monoids with Infinite Promises

Alberto Larrauri , Antoine Mottet , Stanislav \v{Z}ivn\'y This is my paper

Pith reviewed 2026-05-23 03:40 UTC · model grok-4.3

classification 💻 cs.CC

keywords promise constraint satisfactionmonoidscomplexity dichotomyequationsalgebraic approachfinitely generated structurespromise problems

0 comments

The pith

A complexity dichotomy holds for solving equations over monoids when arbitrary relations are added and one monoid may be only finitely generated.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper extends an earlier classification of promise equation-solving problems over finite monoids to two broader settings. It shows that the same algebraic method still produces a clean split between polynomial-time and NP-complete cases once arbitrary relations are permitted on the monoids and the promise monoid is allowed to be finitely generated rather than finite. A reader would care because the result enlarges the family of promise constraint satisfaction problems that receive a complete complexity map without intermediate degrees of difficulty.

Core claim

Using the algebraic approach to promise constraint satisfaction problems, we obtain a complexity dichotomy for the problem of solving a system of equations over a monoid N assuming that a solution exists over a monoid M, where M is finitely generated, both monoids admit a homomorphism in the appropriate direction, and arbitrary relations may be added to either monoid.

What carries the argument

The algebraic approach to promise constraint satisfaction problems, which classifies tractability via the existence of certain homomorphisms between the monoids and their expansions by relations.

If this is right

Every instance of the extended promise equation problem is either in P or NP-complete.
The dichotomy applies uniformly to all finitely generated promise monoids and all expansions by arbitrary relations.
No promise equation problem in this enlarged class requires an intermediate complexity assumption.
The classification remains effective: one can decide which side of the dichotomy a given instance occupies by inspecting the algebraic structure.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same algebraic method may classify still wider classes of promise problems whose domains are infinite but finitely generated.
It suggests that finiteness of both monoids was not essential to the earlier dichotomy and can be relaxed in other promise CSP settings.
Concrete algorithms or hardness reductions from the finite case may transfer directly once the algebraic invariants match.

Load-bearing premise

The algebraic invariants that separated tractable from hard cases in the finite-monoid setting continue to do so once relations are added arbitrarily and the promise monoid need only be finitely generated.

What would settle it

An explicit finitely generated monoid M, monoid N, and set of added relations such that the corresponding promise equation problem is neither solvable in polynomial time nor NP-complete.

read the original abstract

Larrauri and \v{Z}ivn\'y [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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Extends the finite monoid promise equation dichotomy to arbitrary relations and finitely generated M, but the algebraic lift needs verification on whether polymorphisms and obstruction enumeration still work for infinite M.

read the letter

This paper extends the Larrauri-Živný classification for promise equation solving over finite monoids to two broader settings: arbitrary relations added to the monoids, and M allowed to be only finitely generated rather than finite. They claim the algebraic approach to promise CSPs still yields a complete complexity dichotomy in both cases at once. The work does a clean job of stating the two extensions and positioning them as natural next steps from the cited ICALP'25/ToCL'24 result. The citation pattern is straightforward and non-circular, building directly on the prior classification without introducing free parameters or invented entities. The abstract is clear about what is new. The main soft spot is whether the algebraic invariants carry over when M is infinite. Adding arbitrary relations enlarges the polymorphism clone, and it is not obvious that the clone remains finitely generated or that the enumeration of minimal obstructions still terminates. The stress-test concern about new tractable cases or undecidable fragments slipping through the finite-domain tools is worth checking in the full text. If the paper shows explicitly how the reduction and the variety-based classification adapt without extra assumptions, the result holds; if it just lifts the finite argument, that is the place a referee should press. This is for specialists already working on algebraic classifications of promise CSPs. Someone who knows the prior paper will see exactly what changed and where the new proof work is. It deserves peer review because the claim is a direct, non-routine extension of recent work and the community needs to know if the machinery scales.

Referee Report

2 major / 1 minor

Summary. The paper extends the complexity dichotomy of Larrauri and Živný for the promise problem of solving systems of equations over a monoid N given that a solution exists over a monoid M (with M homomorphic to N) to two new settings: (i) arbitrary relations may be added to the monoids, and (ii) M may be any finitely generated monoid (possibly infinite). The extension is obtained via the algebraic approach to promise constraint satisfaction, yielding a complete classification in the enlarged setting.

Significance. If the central claim holds, the result is significant because it enlarges the scope of the algebraic classification technique from finite monoids to finitely generated ones while permitting arbitrary added relations; this would constitute a non-trivial broadening of the promise-CSP dichotomy framework beyond the finite-domain case established in the cited prior work.

major comments (2)

[§3] §3 (main theorem and its proof): the argument lifts the finite-monoid classification directly to the finitely-generated case without an explicit argument that the polymorphism clone of a finitely generated (possibly infinite) monoid remains finitely generated or that the enumeration of minimal obstructions still terminates once arbitrary relations are adjoined; this step is load-bearing for the claimed dichotomy.
[main theorem] The statement that the algebraic invariants continue to classify the problem when M is only finitely generated (rather than finite) is asserted but the manuscript does not supply a concrete verification that the clone-generation or obstruction-listing procedures remain effective; this is required to confirm that no new tractable or undecidable fragments arise.

minor comments (1)

[§2] Notation for the added relations and the homomorphism from M to N should be introduced with an explicit example in the preliminaries to improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments. We address the major comments point by point below.

read point-by-point responses

Referee: [§3] §3 (main theorem and its proof): the argument lifts the finite-monoid classification directly to the finitely-generated case without an explicit argument that the polymorphism clone of a finitely generated (possibly infinite) monoid remains finitely generated or that the enumeration of minimal obstructions still terminates once arbitrary relations are adjoined; this step is load-bearing for the claimed dichotomy.

Authors: We agree that the lifting argument in §3 would benefit from greater explicitness. The proof relies on the fact that finite generation of M (by a finite set of generators) implies that the polymorphisms of the structure are generated by a finite collection of operations obtained by composing the monoid multiplication with the generators and the added relations; the obstruction enumeration then terminates because the promise homomorphism to M restricts the minimal forbidden substructures to a finite list preservable by this clone. We will revise the manuscript to include a short clarifying lemma or paragraph making this reduction explicit. revision: yes
Referee: [main theorem] The statement that the algebraic invariants continue to classify the problem when M is only finitely generated (rather than finite) is asserted but the manuscript does not supply a concrete verification that the clone-generation or obstruction-listing procedures remain effective; this is required to confirm that no new tractable or undecidable fragments arise.

Authors: We accept the referee's observation that a concrete verification of effectiveness is not spelled out. In the revised version we will add an explicit argument showing that both the clone-generation procedure (via finite generators of M) and the obstruction-listing procedure remain effective, thereby confirming that the dichotomy is preserved and that no new complexity fragments appear. revision: yes

Circularity Check

0 steps flagged

Extends prior classification via algebraic approach; self-citation present but not load-bearing on new results

full rationale

The paper explicitly cites and builds upon the finite-monoid classification of Larrauri and Živný (ICALP'25/ACM ToCL'24) to obtain a dichotomy for arbitrary relations and finitely generated (possibly infinite) M. The extension itself supplies independent content rather than reducing by construction to the prior inputs, fitted parameters, or self-definitional equations. No quoted derivation in the abstract or reader's summary exhibits a reduction of the form 'prediction equals input by definition' or an unverified uniqueness theorem imported solely from overlapping-author prior work. This matches the default expectation of minor self-citation without circularity in the central claim.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; review limited to abstract so ledger is empty.

pith-pipeline@v0.9.0 · 5634 in / 845 out tokens · 21769 ms · 2026-05-23T03:40:39.863346+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 3.1. Let M = (M, RM), N = (N, RN) be expansions of monoids such that M → N. Assume that M is finitely generated and N is finite. Then, either (1) there exists a homomorphism h: M → N with a regular commutative image such that r h(RM) s ⊆ RN and PCSP(M,N) is solvable in polynomial time, or (2) PCSP(M,N) is NP-hard.
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We show that the CSP of an expansion of a finitely generated regular commutative monoid by any finite number of cosets is solvable in polynomial time.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

[1]

Finitely tractable promise constraint satisfaction problems

Kristina Asimi and Libor Barto. Finitely tractable promise constraint satisfaction problems. InProc. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS’21), volume 202 ofLIPIcs, pages 11:1–11:16. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2021. arXiv:2010.04618,doi:10.4230/LIPIcs.MFCS.2021.11

work page doi:10.4230/lipics.mfcs.2021.11 2021
[2]

Extensions of unification modulo ACUI.Math

Franz Baader, Pavlos Marantidis, Antoine Mottet, and Alexander Okhotin. Extensions of unification modulo ACUI.Math. Struct. Comput. Sci., 30(6):597–626, 2020. doi:10.1017/ S0960129519000185

work page 2020
[3]

Unification theory

Franz Baader and Wayne Snyder. Unification theory. InHandbook of Automated Reasoning, pages 447–533. Elsevier, 2001

work page 2001
[4]

Krokhin, and Jakub Oprˇ sal

Libor Barto, Jakub Bul´ ın, Andrei A. Krokhin, and Jakub Oprˇ sal. Algebraic approach to promise constraint satisfaction.J. ACM, 68(4):28:1–28:66, 2021. arXiv:1811.00970, doi:10.1145/ 3457606

work page arXiv 2021
[5]

DeMeo, and Antoine Mottet

Libor Barto, William J. DeMeo, and Antoine Mottet. Constraint satisfaction problems over finite structures. InProc. 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’21), pages 1–13. IEEE, 2021.doi:10.1109/LICS52264.2021.9470670

work page doi:10.1109/lics52264.2021.9470670 2021
[6]

Combinatorial Gap Theorem and Reductions between Promise CSPs

Libor Barto and Marcin Kozik. Combinatorial Gap Theorem and Reductions between Promise CSPs. InProc. 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA’22), pages 1204–1220, 2022.arXiv:2107.09423,doi:10.1137/1.9781611977073.50

work page doi:10.1137/1.9781611977073.50 2022
[7]

Finite algebras with hom-sets of polynomial size.Trans

Libor Barto and Antoine Mottet. Finite algebras with hom-sets of polynomial size.Trans. Amer. Math. Soc., 378:569–596, 2025.doi:10.1090/tran/9262. 23

work page doi:10.1090/tran/9262 2025
[8]

The complexity of disjunctive linear Diophantine constraints

Manuel Bodirsky, Barnaby Martin, Marcello Mamino, and Antoine Mottet. The complexity of disjunctive linear Diophantine constraints. InProc. 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS’18), volume 117 ofLIPIcs, pages 33:1–33:16. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2018.doi:10.4230/LIPICS.MFCS.2018.33

work page doi:10.4230/lipics.mfcs.2018.33 2018
[9]

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.SIAM J

Joshua Brakensiek and Venkatesan Guruswami. Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.SIAM J. Comput., 50(6):1663–1700, 2021. arXiv:1704.01937,doi:10.1137/19M128212X

work page doi:10.1137/19m128212x 2021
[10]

The power of the combined basic LP and affine relaxation for promise CSPs.SIAM J

Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav ˇZivn´ y. The power of the combined basic LP and affine relaxation for promise CSPs.SIAM J. Comput., 49:1232–1248, 2020.arXiv:1907.04383,doi:10.1137/20M1312745

work page doi:10.1137/20m1312745 2020
[11]

Optimal inapproximability of promise equations over finite groups

Silvia Butti, Alberto Larrauri, and Stanislav ˇZivn´ y. Optimal inapproximability of promise equations over finite groups. InProc. 52nd International Colloquium on Automata, Languages, and Programming (ICALP’25). Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2025. arXiv: 2411.01630

work page arXiv 2025
[12]

The algebraic theory of semigroups, vol

Alfred H Clifford and Gordon B Preston. The algebraic theory of semigroups, vol. 1.Mathematical surveys, 7, 1961

work page 1961
[13]

The existential theory of equations with rational constraints in free groups is pspace-complete.Inf

Volker Diekert, Claudio Gutierrez, and Christian Hagenah. The existential theory of equations with rational constraints in free groups is pspace-complete.Inf. Comput., 202(2):105–140, 2005. doi:10.1016/J.IC.2005.04.002

work page doi:10.1016/j.ic.2005.04.002 2005
[14]

Inapproximability results for equations over finite groups.Theor

Lars Engebretsen, Jonas Holmerin, and Alexander Russell. Inapproximability results for equations over finite groups.Theor. Comput. Sci., 312(1):17–45, 2004. doi:10.1016/S0304-3975(03) 00401-8

work page doi:10.1016/s0304-3975(03 2004
[15]

Tom´ as Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory.SIAM J. Comput., 28(1):57–104, 1998.doi:10.1137/S0097539794266766

work page doi:10.1137/s0097539794266766 1998
[16]

When symmetries are not enough: A hierarchy of hard constraint satisfaction problems.SIAM J

Pierre Gillibert, Julius Jonusas, Michael Kompatscher, Antoine Mottet, and Michael Pinsker. When symmetries are not enough: A hierarchy of hard constraint satisfaction problems.SIAM J. Comput., 51(2):175–213, 2022.arXiv:2002.07054,doi:10.1137/20M1383471

work page doi:10.1137/20m1383471 2022
[17]

Lozano, A

Christian Glaßer, Peter Jonsson, and Barnaby Martin. Circuit satisfiability and constraint satisfaction around Skolem arithmetic.Theor. Comput. Sci., 703:18–36, 2017. doi:10.1016/j. tcs.2017.08.025

work page doi:10.1016/j 2017
[18]

The complexity of solving equations over finite groups

Mikael Goldmann and Alexander Russell. The complexity of solving equations over finite groups. Inf. Comput., 178(1):253–262, 2002.doi:10.1006/INCO.2002.3173

work page doi:10.1006/inco.2002.3173 2002
[19]

Routledge, 2017

Pierre A Grillet.Semigroups: an introduction to the structure theory. Routledge, 2017

work page 2017
[20]

Some optimal inapproximability results.J

Johan H˚ astad. Some optimal inapproximability results.J. ACM, 48(4):798–859, 2001. doi: 10.1145/502090.502098

work page doi:10.1145/502090.502098 2001
[21]

Oxford University Press, 1995

John M Howie.Fundamentals of semigroup theory. Oxford University Press, 1995

work page 1995
[22]

Springer Science & Business Media, 2012

Thomas W Hungerford.Algebra, volume 73. Springer Science & Business Media, 2012

work page 2012
[23]

Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix.SIAM J

Ravindran Kannan and Achim Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix.SIAM J. Comput., 8(4):499–507, 1979. doi:10.1137/ 0208040

work page 1979
[24]

Dichotomies in the complexity of solving systems of equations over finite semigroups.Theory Comput

Ondˇ rej Kl´ ıma, Pascal Tesson, and Denis Th´ erien. Dichotomies in the complexity of solving systems of equations over finite semigroups.Theory Comput. Syst., 40(3):263–297, 2007. doi: 10.1007/S00224-005-1279-2. 24

work page doi:10.1007/s00224-005-1279-2 2007
[25]

An invitation to the promise constraint satisfaction problem

Andrei Krokhin and Jakub Oprˇ sal. An invitation to the promise constraint satisfaction problem. ACM SIGLOG News, 9(3):30–59, 2022.arXiv:2208.13538

work page arXiv 2022
[26]

Solving promise equations over monoids and groups.ACM Trans

Alberto Larrauri and Stanislav ˇZivn´ y. Solving promise equations over monoids and groups.ACM Trans. Comput. Log., 26(1):1–24, 2024.arXiv:2402.08434,doi:10.1145/3698106

work page doi:10.1145/3698106 2024
[27]

Algebraic and algorithmic synergies between promise and infinite-domain CSPs

Antoine Mottet. Algebraic and algorithmic synergies between promise and infinite-domain CSPs. InProc. 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’25). IEEE, 2025.arXiv:2501.13740

work page arXiv 2025
[28]

Satisfiability of word equations with constants is in PSPACE.J

Wojciech Plandowski. Satisfiability of word equations with constants is in PSPACE.J. ACM, 51(3):483–496, 2004.doi:10.1145/990308.990312. 25

work page doi:10.1145/990308.990312 2004

[1] [1]

Finitely tractable promise constraint satisfaction problems

Kristina Asimi and Libor Barto. Finitely tractable promise constraint satisfaction problems. InProc. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS’21), volume 202 ofLIPIcs, pages 11:1–11:16. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2021. arXiv:2010.04618,doi:10.4230/LIPIcs.MFCS.2021.11

work page doi:10.4230/lipics.mfcs.2021.11 2021

[2] [2]

Extensions of unification modulo ACUI.Math

Franz Baader, Pavlos Marantidis, Antoine Mottet, and Alexander Okhotin. Extensions of unification modulo ACUI.Math. Struct. Comput. Sci., 30(6):597–626, 2020. doi:10.1017/ S0960129519000185

work page 2020

[3] [3]

Unification theory

Franz Baader and Wayne Snyder. Unification theory. InHandbook of Automated Reasoning, pages 447–533. Elsevier, 2001

work page 2001

[4] [4]

Krokhin, and Jakub Oprˇ sal

Libor Barto, Jakub Bul´ ın, Andrei A. Krokhin, and Jakub Oprˇ sal. Algebraic approach to promise constraint satisfaction.J. ACM, 68(4):28:1–28:66, 2021. arXiv:1811.00970, doi:10.1145/ 3457606

work page arXiv 2021

[5] [5]

DeMeo, and Antoine Mottet

Libor Barto, William J. DeMeo, and Antoine Mottet. Constraint satisfaction problems over finite structures. InProc. 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’21), pages 1–13. IEEE, 2021.doi:10.1109/LICS52264.2021.9470670

work page doi:10.1109/lics52264.2021.9470670 2021

[6] [6]

Combinatorial Gap Theorem and Reductions between Promise CSPs

Libor Barto and Marcin Kozik. Combinatorial Gap Theorem and Reductions between Promise CSPs. InProc. 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA’22), pages 1204–1220, 2022.arXiv:2107.09423,doi:10.1137/1.9781611977073.50

work page doi:10.1137/1.9781611977073.50 2022

[7] [7]

Finite algebras with hom-sets of polynomial size.Trans

Libor Barto and Antoine Mottet. Finite algebras with hom-sets of polynomial size.Trans. Amer. Math. Soc., 378:569–596, 2025.doi:10.1090/tran/9262. 23

work page doi:10.1090/tran/9262 2025

[8] [8]

The complexity of disjunctive linear Diophantine constraints

Manuel Bodirsky, Barnaby Martin, Marcello Mamino, and Antoine Mottet. The complexity of disjunctive linear Diophantine constraints. InProc. 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS’18), volume 117 ofLIPIcs, pages 33:1–33:16. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2018.doi:10.4230/LIPICS.MFCS.2018.33

work page doi:10.4230/lipics.mfcs.2018.33 2018

[9] [9]

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.SIAM J

Joshua Brakensiek and Venkatesan Guruswami. Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.SIAM J. Comput., 50(6):1663–1700, 2021. arXiv:1704.01937,doi:10.1137/19M128212X

work page doi:10.1137/19m128212x 2021

[10] [10]

The power of the combined basic LP and affine relaxation for promise CSPs.SIAM J

Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav ˇZivn´ y. The power of the combined basic LP and affine relaxation for promise CSPs.SIAM J. Comput., 49:1232–1248, 2020.arXiv:1907.04383,doi:10.1137/20M1312745

work page doi:10.1137/20m1312745 2020

[11] [11]

Optimal inapproximability of promise equations over finite groups

Silvia Butti, Alberto Larrauri, and Stanislav ˇZivn´ y. Optimal inapproximability of promise equations over finite groups. InProc. 52nd International Colloquium on Automata, Languages, and Programming (ICALP’25). Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2025. arXiv: 2411.01630

work page arXiv 2025

[12] [12]

The algebraic theory of semigroups, vol

Alfred H Clifford and Gordon B Preston. The algebraic theory of semigroups, vol. 1.Mathematical surveys, 7, 1961

work page 1961

[13] [13]

The existential theory of equations with rational constraints in free groups is pspace-complete.Inf

Volker Diekert, Claudio Gutierrez, and Christian Hagenah. The existential theory of equations with rational constraints in free groups is pspace-complete.Inf. Comput., 202(2):105–140, 2005. doi:10.1016/J.IC.2005.04.002

work page doi:10.1016/j.ic.2005.04.002 2005

[14] [14]

Inapproximability results for equations over finite groups.Theor

Lars Engebretsen, Jonas Holmerin, and Alexander Russell. Inapproximability results for equations over finite groups.Theor. Comput. Sci., 312(1):17–45, 2004. doi:10.1016/S0304-3975(03) 00401-8

work page doi:10.1016/s0304-3975(03 2004

[15] [15]

Tom´ as Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory.SIAM J. Comput., 28(1):57–104, 1998.doi:10.1137/S0097539794266766

work page doi:10.1137/s0097539794266766 1998

[16] [16]

When symmetries are not enough: A hierarchy of hard constraint satisfaction problems.SIAM J

Pierre Gillibert, Julius Jonusas, Michael Kompatscher, Antoine Mottet, and Michael Pinsker. When symmetries are not enough: A hierarchy of hard constraint satisfaction problems.SIAM J. Comput., 51(2):175–213, 2022.arXiv:2002.07054,doi:10.1137/20M1383471

work page doi:10.1137/20m1383471 2022

[17] [17]

Lozano, A

Christian Glaßer, Peter Jonsson, and Barnaby Martin. Circuit satisfiability and constraint satisfaction around Skolem arithmetic.Theor. Comput. Sci., 703:18–36, 2017. doi:10.1016/j. tcs.2017.08.025

work page doi:10.1016/j 2017

[18] [18]

The complexity of solving equations over finite groups

Mikael Goldmann and Alexander Russell. The complexity of solving equations over finite groups. Inf. Comput., 178(1):253–262, 2002.doi:10.1006/INCO.2002.3173

work page doi:10.1006/inco.2002.3173 2002

[19] [19]

Routledge, 2017

Pierre A Grillet.Semigroups: an introduction to the structure theory. Routledge, 2017

work page 2017

[20] [20]

Some optimal inapproximability results.J

Johan H˚ astad. Some optimal inapproximability results.J. ACM, 48(4):798–859, 2001. doi: 10.1145/502090.502098

work page doi:10.1145/502090.502098 2001

[21] [21]

Oxford University Press, 1995

John M Howie.Fundamentals of semigroup theory. Oxford University Press, 1995

work page 1995

[22] [22]

Springer Science & Business Media, 2012

Thomas W Hungerford.Algebra, volume 73. Springer Science & Business Media, 2012

work page 2012

[23] [23]

Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix.SIAM J

Ravindran Kannan and Achim Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix.SIAM J. Comput., 8(4):499–507, 1979. doi:10.1137/ 0208040

work page 1979

[24] [24]

Dichotomies in the complexity of solving systems of equations over finite semigroups.Theory Comput

Ondˇ rej Kl´ ıma, Pascal Tesson, and Denis Th´ erien. Dichotomies in the complexity of solving systems of equations over finite semigroups.Theory Comput. Syst., 40(3):263–297, 2007. doi: 10.1007/S00224-005-1279-2. 24

work page doi:10.1007/s00224-005-1279-2 2007

[25] [25]

An invitation to the promise constraint satisfaction problem

Andrei Krokhin and Jakub Oprˇ sal. An invitation to the promise constraint satisfaction problem. ACM SIGLOG News, 9(3):30–59, 2022.arXiv:2208.13538

work page arXiv 2022

[26] [26]

Solving promise equations over monoids and groups.ACM Trans

Alberto Larrauri and Stanislav ˇZivn´ y. Solving promise equations over monoids and groups.ACM Trans. Comput. Log., 26(1):1–24, 2024.arXiv:2402.08434,doi:10.1145/3698106

work page doi:10.1145/3698106 2024

[27] [27]

Algebraic and algorithmic synergies between promise and infinite-domain CSPs

Antoine Mottet. Algebraic and algorithmic synergies between promise and infinite-domain CSPs. InProc. 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’25). IEEE, 2025.arXiv:2501.13740

work page arXiv 2025

[28] [28]

Satisfiability of word equations with constants is in PSPACE.J

Wojciech Plandowski. Satisfiability of word equations with constants is in PSPACE.J. ACM, 51(3):483–496, 2004.doi:10.1145/990308.990312. 25

work page doi:10.1145/990308.990312 2004