English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 so 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 the 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.

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras