SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks

Aleksandar Proki\'c; Mikl\'os Mar\'oti; Petar Markovi\'c; Ralph McKenzie

arxiv: 2604.05161 · v1 · submitted 2026-04-06 · 💻 cs.CC · cs.LO· math.LO

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks

Petar Markovi\'c , Mikl\'os Mar\'oti , Ralph McKenzie , Aleksandar Proki\'c This is my paper

Pith reviewed 2026-05-10 18:41 UTC · model grok-4.3

classification 💻 cs.CC cs.LOmath.LO

keywords SMB algebrassemilattices of Mal'cev blocksconstraint satisfaction problemCSP tractabilityCSP dichotomyMal'cev algebrassemilattices

0 comments

The pith

All semilattices of Mal'cev blocks induce tractable templates for the constraint satisfaction problem.

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

This paper defines SMB algebras as semilattices in which each element is replaced by a Mal'cev algebra. The authors publish proofs that certain SMB algebras yield tractable CSP templates and then reprove the general result that every such algebra does so, matching a prior theorem by Bulatov. They also examine the two main proofs of the CSP dichotomy theorem and demonstrate that the proofs become more similar when both are applied specifically to SMB algebras. A sympathetic reader cares because the work clarifies algebraic conditions for tractability and reveals unexpected alignments between distinct proof strategies.

Core claim

We define a class of algebras called semilattices of Mal'cev blocks, or SMB algebras, in which a semilattice structure has each element expanded into a Mal'cev algebra. We give our earlier proofs that some SMB algebras induce tractable CSP templates, and we reprove that in fact all SMB algebras induce tractable templates, a result first shown by Bulatov. When the two general proofs of the CSP Dichotomy are specialized to SMB algebras, they prove more similar than they initially appear.

What carries the argument

The semilattice of Mal'cev blocks (SMB algebra), formed by taking a semilattice and replacing each element with a Mal'cev algebra so that the overall structure satisfies the identities needed for CSP tractability proofs.

If this is right

The constraint satisfaction problem over any SMB algebra admits a polynomial-time algorithm.
Special cases of SMB algebras previously studied by the authors are tractable.
The two general CSP dichotomy proofs align closely when restricted to the SMB class.
SMB algebras provide a concrete setting in which to test and compare different algebraic approaches to tractability.

Where Pith is reading between the lines

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

SMB algebras may serve as a useful test class for exploring whether other algebraic structures exhibit similar convergence between distinct dichotomy proofs.
The observed similarity between proofs on this class could motivate systematic comparisons on larger families of algebras.
One could investigate whether the tractability of SMB algebras extends to natural generalizations that preserve the semilattice-plus-Mal'cev-block structure.

Load-bearing premise

The defined class of SMB algebras satisfies the algebraic identities required for existing tractability proofs to apply directly without extra restrictions.

What would settle it

An explicit construction of an SMB algebra whose associated CSP template is NP-complete would disprove the central claim.

read the original abstract

We define a class of algebras, the semilattices of Mal'cev blocks (for short, SMB algebras). In a nutshell, these algebras are semilattices in which each element gets blown up into a Mal'cev algebra. We publish for the first time our old proofs that some SMB algebras induce tractable templates of the reprove that the Constraint Satisfaction Problem. Next, we reprove that, in fact, all SMB algebras induce tractable templates of the Constraint Satisfaction Problem, a result already proved by A. Bulatov. Also, we compare the two general proofs of the CSP Dichotomy and prove they are more similar than initially thought when they are applied to SMB algebras. This paper is the second in the series of papers investigating the SMB algebras and it is a precursor to our further research on the similarities between the proofs of the Dichotomy Theorem.

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

This paper is a reproof of Bulatov's known tractability result for all SMB algebras plus a comparison of two CSP dichotomy proofs on that class, with some older partial proofs now published.

read the letter

The main point is that every SMB algebra gives a tractable CSP template, but that fact was already established by Bulatov. The authors say so directly. What is new here is that they release some older partial proofs they had for special cases of SMB algebras and then restrict both general dichotomy proofs to this class to argue that the two proofs end up more similar than they look at first glance. The definition of SMB algebras as semilattices with each element replaced by a Mal'cev algebra is laid out, along with the identities that let the tractability arguments go through without extra restrictions. That comparison section is the part that could actually help readers who are trying to see how the general techniques specialize. If the similarity is shown with concrete steps rather than just high-level remarks, it might clarify why both proofs succeed on this family. The paper is the second in their series on SMB algebras and positions itself as groundwork for later work on proof similarities. The soft spot is that the central claim is a reproof, so the paper's contribution hinges on whether the comparison delivers real insight or stays mostly descriptive. No load-bearing gaps appear in the setup from the definitions and identities given, and there is no circularity or self-referential fitting. This is for people already working inside the algebraic CSP classification program who want to see the proofs restricted to a concrete, natural subclass or who follow the authors' series. A reader outside that niche will not get much from it. I would send it to referees. The comparison is worth checking even though the tractability result is not new, and the work shows clear engagement with the existing literature.

Referee Report

0 major / 2 minor

Summary. The manuscript defines a class of algebras called semilattices of Mal'cev blocks (SMB algebras), consisting of semilattices in which each element is replaced by a Mal'cev algebra. It presents proofs that certain SMB algebras induce tractable CSP templates, reproves that all SMB algebras induce tractable CSP templates (a result originally due to Bulatov), and compares the two general proofs of the CSP dichotomy theorem when restricted to the SMB domain, arguing that the proofs are more similar than initially apparent.

Significance. If the explicit definitions, algebraic identities, and comparative analysis hold, the work provides a concrete case study that may clarify the mechanisms underlying tractability in CSPs and the relationships between distinct proof strategies for the dichotomy theorem. The publication of previously unpublished partial proofs together with the side-by-side comparison on a restricted but nontrivial class could serve as a useful reference for researchers examining algebraic approaches to CSP complexity.

minor comments (2)

[Abstract] Abstract: the sentence beginning 'We publish for the first time our old proofs that some SMB algebras induce tractable templates of the reprove that the Constraint Satisfaction Problem' is garbled and should be rewritten to clearly distinguish the presentation of the partial results from the full reproof of Bulatov's theorem.
The manuscript would benefit from explicit pointers (e.g., 'see §3.2' or 'see Theorem 4.1') when the algebraic identities required for the tractability proofs are first verified and when the comparison between the two dichotomy proofs is summarized.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review of our manuscript on semilattices of Mal'cev blocks (SMB algebras), the accurate summary of its contributions, and the recommendation for minor revision. The significance assessment is appreciated, as the work aims to provide a concrete case study clarifying tractability mechanisms and relationships between CSP dichotomy proofs on this restricted class. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained reproof with explicit definitions and independent proofs

full rationale

The paper explicitly defines the class of SMB algebras as semilattices with Mal'cev blocks and supplies its own algebraic proofs that all such algebras yield tractable CSP templates. It acknowledges Bulatov's prior result as external and compares the two general dichotomy proofs on this domain without reducing the central claim to a self-citation chain, fitted parameter, or definitional equivalence. The derivation chain consists of direct verification of algebraic identities and tractability conditions, which are independent of the inputs by construction. No load-bearing step matches any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 1 invented entities

The paper introduces the new class of SMB algebras by combining semilattices and Mal'cev algebras; no free parameters, standard axioms, or invented entities with independent evidence are described in the abstract.

invented entities (1)

SMB algebras (semilattices of Mal'cev blocks) no independent evidence
purpose: To define a class of algebras for which CSP templates are tractable
Defined in the abstract as semilattices in which each element is blown up into a Mal'cev algebra; no independent evidence or falsifiable prediction outside the paper is mentioned.

pith-pipeline@v0.9.0 · 5473 in / 1384 out tokens · 40290 ms · 2026-05-10T18:41:17.467124+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

[1]

Barto, L.: The collapse of the bounded width hierarchy. J. Logic Comput.26, 923–943 (2016)

work page 2016
[2]

Barto, L.: Finitely related algebras in congruence modular varieties have few sub- powers. J. Eur. Math. Soc.20, 1439–1471 (2018)

work page 2018
[3]

org/abs/2104.11808

Barto, L., Brady, Z, Bulatov, A., Kozik, M., Zhuk, D.: Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras, manuscript.https://arxiv. org/abs/2104.11808

work page arXiv
[4]

Journal of the ACM611:03, 19 pp., (2014)

Barto, L., Kozik, M.: Constraint satisfaction problems solvable by local consistency methods. Journal of the ACM611:03, 19 pp., (2014)

work page 2014
[5]

Berman, J., Idziak, P., Markovi´ c, P., McKenzie, R., Valeriote, M., Willard, R.: Vari- eties with few subalgebras of powers. Trans. Amer. Math. Soc.3621445–1473 (2010)

work page 2010
[6]

Bulatov, A.: A dichotomy theorem for constraints on a three-element set. J. ACM 53, 66–120 (2006)

work page 2006
[7]

[Russian] Algebra i Logika,45655– 686 (2006)

Bulatov, A.: Complexity of Maltsev Constraints. [Russian] Algebra i Logika,45655– 686 (2006)

work page 2006
[8]

ACM Trans

Bulatov, A.: Complexity of Conservative Constraint Satisfaction Problems. ACM Trans. Comput. Logic12Article no. 24 66pp. (2011)

work page 2011
[9]

104437, 14 pp., (2019)

Bulatov, A.: Constraint Satisfaction Problems over semilattice block Mal’tsev alge- bras, Information and Computation268Article no. 104437, 14 pp., (2019)

work page 2019
[10]

org/abs/2006.09599

Bulatov, A.: Local structure of idempotent algebras I, manuscript.https://arxiv. org/abs/2006.09599

work page arXiv 2006
[11]

org/abs/2006.10239 54 P

Bulatov, A.: Local structure of idempotent algebras II, manuscript.https://arxiv. org/abs/2006.10239 54 P. MARKOVI ´C, M. MAR ´OTI, R. MCKENZIE, AND A. PROKI ´C

work page arXiv 2006
[12]

In: Proc

Bulatov, A.: Graphs of relational structures: restricted types. In: Proc. 31th IEEE Ann. Symp. on Logic in Comput. Sci. (LICS) New York, USA, 2016, pp. 642–651. doi: 10.1145/2933575.2933604 IEEE Computer Society, ISBN:978-1-4503-4391-6

work page doi:10.1145/2933575.2933604 2016
[13]

11 Andrei A

Bulatov, A.: A dichotomy theorem for nonuniform CSPs In: Proc. 2017 IEEE 58th Annual Symp. on Foundations of Comput. Sci. (FOCS), Berkeley, CA (USA, October 2017), pp. 319-330, doi: 10.1109/FOCS.2017.37, IEEE Computer Society Conference Publishing Service Los Alamitos, CA

work page doi:10.1109/focs.2017.37 2017
[14]

Bulatov, A.: A dichotomy theorem for nonuniform CSPs, manuscript.https: //arxiv.org/abs/1703.03021

work page arXiv
[15]

(eds) Language and Automata Theory and Applications

Bulatov, A.: Constraint Satisfaction Problems: Complexity and Algorithms, In: Klein, S., Mart´ ın-Vide, C., Shapira, D. (eds) Language and Automata Theory and Applications. LATA 2018. Ramat Gan, (Israel, April 2018), pp. 1–25, doi: 10.1007/978-3-319-77313-1 Lecture Notes in Comput. Sci., vol 10792, (2018) Springer, New York

work page doi:10.1007/978-3-319-77313-1 2018
[16]

Bulatov A., Dalmau, V.: Mal’tsev constraints are tractable. SIAM J. Comput.36 16–27 (2006)

work page 2006
[17]

Bulatov, A., Jeavons P., Krokhin, A., Classifying the complexity of constraints using finite algebras. SIAM J. Comp.34720–742 (2005)

work page 2005
[18]

Bulin, J., Deli´ c, D., Jackson M., Niven, T.: A finer reduction of constraint problems to digraphs. Log. Meth. Comput. Sci.11, Article no. 18, 33 pp. (2015)

work page 2015
[19]

Graduate Texts in Mathematics, vol

Burris, S., Sankappanavar, H.P.: A course in universal algebra. Graduate Texts in Mathematics, vol. 78. Springer, New York (1981)

work page 1981
[20]

manuscript

-Dapi´ c, P., Markovi´ c, P., McKenzie, R., Proki´ c A.: SMB Algebras I: On the variety of SMB algebras. manuscript

work page
[21]

Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory

Feder, T., Vardi, M. Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM J. Comput.2857–104 (1999)

work page 1999
[22]

Contemporary Mathemat- ics, vol

Hobby, D., McKenzie, R.: The structure of finite algebras. Contemporary Mathemat- ics, vol. 76. American Mathematical Society, Providence (1988)

work page 1988
[23]

Idziak, P., Markovi´ c, P., McKenzie, R., Valeriote, M., Willard, R.: Tractability and learnability arising from algebra with few subpowers. SIAM J. Comput.39, 3023– 3037 (2010)

work page 2010
[24]

G.: On the algebraic structure of combinatorial problems

Jeavons, P. G.: On the algebraic structure of combinatorial problems. Theor. Comp. Sci.200185–204 (1998)

work page 1998
[25]

Kun, G.: Constraints, MMSNP, and Expander Relational Structures Combinatorica 33335–347 (2013)

work page 2013
[26]

(early version untitled), manuscript

Markovi´ c, P., McKenzie, R.: On the Constraint Satisfaction Problem over semilattices of Mal’cev blocks. (early version untitled), manuscript

work page
[27]

Mar´ oti, Maltsev on top

M. Mar´ oti, Maltsev on top. manuscript,http://www.math.u-szeged.hu/ ~mmaroti/ pdf/200x%20Maltsev%20on%20top.pdf

work page
[28]

Mar´ oti, M.: Tree on top of Maltsev, manuscript.http://www.math.u-szeged.hu/ ~mmaroti/pdf/200x%20Tree%20on%20top%20of%20Maltsev.pdf

work page
[29]

N.: Existence theorems for weakly symmetric operations

Mar´ oti, M., McKenzie, R. N.: Existence theorems for weakly symmetric operations. Algebra Universalis59463–489 (2008)

work page 2008
[30]

McKenzie, R., McNulty, G., Taylor, W.: Algebras, lattices, varieties. Vol. I. The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Ad- vanced Books & Software, Monterey (1987)

work page 1987
[31]

A Proof of

Zhuk, D.: A proof of CSP dichotomy conjecture, In: Proc. 2017 IEEE 58th An- nual Symp. on Foundations of Comput. Sci. (FOCS), Berkeley, CA (USA, October 2017), pp. 331-342, doi: 10.1109/FOCS.2017.38, IEEE Computer Society Conference Publishing Service Los Alamitos, CA

work page doi:10.1109/focs.2017.38 2017
[32]

Zhuk, D.: A Proof of the CSP Dichotomy Conjecture, Journal of the ACM675:30, 78 pp., (2020) SMB ALGEBRAS II 55 Department of Mathematics and Informatics, University of Novi Sad, Ser- bia Email address, Petar Markovi´ c:pera@dmi.uns.ac.rs Bolyai Institute, University of Szeged, Hungary Email address, Mikl´ os Mar´ oti:mmaroti@math.u-szeged.hu Department of...

work page 2020

[1] [1]

Barto, L.: The collapse of the bounded width hierarchy. J. Logic Comput.26, 923–943 (2016)

work page 2016

[2] [2]

Barto, L.: Finitely related algebras in congruence modular varieties have few sub- powers. J. Eur. Math. Soc.20, 1439–1471 (2018)

work page 2018

[3] [3]

org/abs/2104.11808

Barto, L., Brady, Z, Bulatov, A., Kozik, M., Zhuk, D.: Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras, manuscript.https://arxiv. org/abs/2104.11808

work page arXiv

[4] [4]

Journal of the ACM611:03, 19 pp., (2014)

Barto, L., Kozik, M.: Constraint satisfaction problems solvable by local consistency methods. Journal of the ACM611:03, 19 pp., (2014)

work page 2014

[5] [5]

Berman, J., Idziak, P., Markovi´ c, P., McKenzie, R., Valeriote, M., Willard, R.: Vari- eties with few subalgebras of powers. Trans. Amer. Math. Soc.3621445–1473 (2010)

work page 2010

[6] [6]

Bulatov, A.: A dichotomy theorem for constraints on a three-element set. J. ACM 53, 66–120 (2006)

work page 2006

[7] [7]

[Russian] Algebra i Logika,45655– 686 (2006)

Bulatov, A.: Complexity of Maltsev Constraints. [Russian] Algebra i Logika,45655– 686 (2006)

work page 2006

[8] [8]

ACM Trans

Bulatov, A.: Complexity of Conservative Constraint Satisfaction Problems. ACM Trans. Comput. Logic12Article no. 24 66pp. (2011)

work page 2011

[9] [9]

104437, 14 pp., (2019)

Bulatov, A.: Constraint Satisfaction Problems over semilattice block Mal’tsev alge- bras, Information and Computation268Article no. 104437, 14 pp., (2019)

work page 2019

[10] [10]

org/abs/2006.09599

Bulatov, A.: Local structure of idempotent algebras I, manuscript.https://arxiv. org/abs/2006.09599

work page arXiv 2006

[11] [11]

org/abs/2006.10239 54 P

Bulatov, A.: Local structure of idempotent algebras II, manuscript.https://arxiv. org/abs/2006.10239 54 P. MARKOVI ´C, M. MAR ´OTI, R. MCKENZIE, AND A. PROKI ´C

work page arXiv 2006

[12] [12]

In: Proc

Bulatov, A.: Graphs of relational structures: restricted types. In: Proc. 31th IEEE Ann. Symp. on Logic in Comput. Sci. (LICS) New York, USA, 2016, pp. 642–651. doi: 10.1145/2933575.2933604 IEEE Computer Society, ISBN:978-1-4503-4391-6

work page doi:10.1145/2933575.2933604 2016

[13] [13]

11 Andrei A

Bulatov, A.: A dichotomy theorem for nonuniform CSPs In: Proc. 2017 IEEE 58th Annual Symp. on Foundations of Comput. Sci. (FOCS), Berkeley, CA (USA, October 2017), pp. 319-330, doi: 10.1109/FOCS.2017.37, IEEE Computer Society Conference Publishing Service Los Alamitos, CA

work page doi:10.1109/focs.2017.37 2017

[14] [14]

Bulatov, A.: A dichotomy theorem for nonuniform CSPs, manuscript.https: //arxiv.org/abs/1703.03021

work page arXiv

[15] [15]

(eds) Language and Automata Theory and Applications

Bulatov, A.: Constraint Satisfaction Problems: Complexity and Algorithms, In: Klein, S., Mart´ ın-Vide, C., Shapira, D. (eds) Language and Automata Theory and Applications. LATA 2018. Ramat Gan, (Israel, April 2018), pp. 1–25, doi: 10.1007/978-3-319-77313-1 Lecture Notes in Comput. Sci., vol 10792, (2018) Springer, New York

work page doi:10.1007/978-3-319-77313-1 2018

[16] [16]

Bulatov A., Dalmau, V.: Mal’tsev constraints are tractable. SIAM J. Comput.36 16–27 (2006)

work page 2006

[17] [17]

Bulatov, A., Jeavons P., Krokhin, A., Classifying the complexity of constraints using finite algebras. SIAM J. Comp.34720–742 (2005)

work page 2005

[18] [18]

Bulin, J., Deli´ c, D., Jackson M., Niven, T.: A finer reduction of constraint problems to digraphs. Log. Meth. Comput. Sci.11, Article no. 18, 33 pp. (2015)

work page 2015

[19] [19]

Graduate Texts in Mathematics, vol

Burris, S., Sankappanavar, H.P.: A course in universal algebra. Graduate Texts in Mathematics, vol. 78. Springer, New York (1981)

work page 1981

[20] [20]

manuscript

-Dapi´ c, P., Markovi´ c, P., McKenzie, R., Proki´ c A.: SMB Algebras I: On the variety of SMB algebras. manuscript

work page

[21] [21]

Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory

Feder, T., Vardi, M. Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM J. Comput.2857–104 (1999)

work page 1999

[22] [22]

Contemporary Mathemat- ics, vol

Hobby, D., McKenzie, R.: The structure of finite algebras. Contemporary Mathemat- ics, vol. 76. American Mathematical Society, Providence (1988)

work page 1988

[23] [23]

Idziak, P., Markovi´ c, P., McKenzie, R., Valeriote, M., Willard, R.: Tractability and learnability arising from algebra with few subpowers. SIAM J. Comput.39, 3023– 3037 (2010)

work page 2010

[24] [24]

G.: On the algebraic structure of combinatorial problems

Jeavons, P. G.: On the algebraic structure of combinatorial problems. Theor. Comp. Sci.200185–204 (1998)

work page 1998

[25] [25]

Kun, G.: Constraints, MMSNP, and Expander Relational Structures Combinatorica 33335–347 (2013)

work page 2013

[26] [26]

(early version untitled), manuscript

Markovi´ c, P., McKenzie, R.: On the Constraint Satisfaction Problem over semilattices of Mal’cev blocks. (early version untitled), manuscript

work page

[27] [27]

Mar´ oti, Maltsev on top

M. Mar´ oti, Maltsev on top. manuscript,http://www.math.u-szeged.hu/ ~mmaroti/ pdf/200x%20Maltsev%20on%20top.pdf

work page

[28] [28]

Mar´ oti, M.: Tree on top of Maltsev, manuscript.http://www.math.u-szeged.hu/ ~mmaroti/pdf/200x%20Tree%20on%20top%20of%20Maltsev.pdf

work page

[29] [29]

N.: Existence theorems for weakly symmetric operations

Mar´ oti, M., McKenzie, R. N.: Existence theorems for weakly symmetric operations. Algebra Universalis59463–489 (2008)

work page 2008

[30] [30]

McKenzie, R., McNulty, G., Taylor, W.: Algebras, lattices, varieties. Vol. I. The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Ad- vanced Books & Software, Monterey (1987)

work page 1987

[31] [31]

A Proof of

Zhuk, D.: A proof of CSP dichotomy conjecture, In: Proc. 2017 IEEE 58th An- nual Symp. on Foundations of Comput. Sci. (FOCS), Berkeley, CA (USA, October 2017), pp. 331-342, doi: 10.1109/FOCS.2017.38, IEEE Computer Society Conference Publishing Service Los Alamitos, CA

work page doi:10.1109/focs.2017.38 2017

[32] [32]

Zhuk, D.: A Proof of the CSP Dichotomy Conjecture, Journal of the ACM675:30, 78 pp., (2020) SMB ALGEBRAS II 55 Department of Mathematics and Informatics, University of Novi Sad, Ser- bia Email address, Petar Markovi´ c:pera@dmi.uns.ac.rs Bolyai Institute, University of Szeged, Hungary Email address, Mikl´ os Mar´ oti:mmaroti@math.u-szeged.hu Department of...

work page 2020