Fiche du document
15 mai 2024
- handle: 10670/1.xa0pfv
- doi: 10.46298/theoretics.24.14
info:eu-repo/semantics/openAccess , info:eu-repo/semantics/openAccess
Citer ce document
Libor Barto et al., « Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras », Episciences.org, ID : 10.46298/theoretics.24.14
Métriques
Partage / Export
Résumé
This paper focuses on the algebraic theory underlying the study of thecomplexity and the algorithms for the Constraint Satisfaction Problem (CSP). Weunify, simplify, and extend parts of the three approaches that have beendeveloped to study the CSP over finite templates -- absorption theory that wasused to characterize CSPs solvable by local consistency methods (JACM'14), andBulatov's and Zhuk's theories that were used for two independent proofs of theCSP Dichotomy Theorem (FOCS'17, JACM'20). As the first contribution we present an elementary theorem about primitivepositive definability and use it to obtain the starting points of Bulatov's andZhuk's proofs as corollaries. As the second contribution we propose andinitiate a systematic study of minimal Taylor algebras. This class of algebrasis broad enough that it suffices to verify the CSP Dichotomy Theorem on thisclass only, but still is unusually well behaved. In particular, many conceptsfrom the three approaches coincide in this class, which is in striking contrastwith the general setting. We believe that the theory initiated in this paper will eventually result ina simple and more natural proof of the Dichotomy Theorem that employs a simplerand more efficient algorithm, and will help in attacking complexity questionsin other CSP-related problems.