SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913009348116480 |
|---|---|
| author | Marković, Petar Maróti, Miklós McKenzie, Ralph Prokić, Aleksandar |
| author_facet | Marković, Petar Maróti, Miklós McKenzie, Ralph Prokić, Aleksandar |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_05161 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks Marković, Petar Maróti, Miklós McKenzie, Ralph Prokić, Aleksandar Computational Complexity Logic in Computer Science Logic 68Q25 (Primary) 08A70, 68Q17, 68Q19 (Secondary) 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. |
| title | SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks |
| topic | Computational Complexity Logic in Computer Science Logic 68Q25 (Primary) 08A70, 68Q17, 68Q19 (Secondary) |
| url | https://arxiv.org/abs/2604.05161 |