A categorical perspective on constraint satisfaction: The wonderland of adjunctions
For researchers in constraint satisfaction and category theory, this work offers a new foundational perspective that simplifies existing proofs and may enable future advances in PCSP complexity.
This paper provides a categorical reformulation of the algebraic approach to constraint satisfaction problems (CSPs) and promise constraint satisfaction problems (PCSPs), showing that standard notions like polymorphisms correspond to categorical concepts such as right Kan extensions. The authors give shorter, cleaner proofs of core results, including that complexity depends only on polymorphisms, and argue that this perspective can help address current challenges in PCSPs.
The so-called algebraic approach to the constraint satisfaction problem (CSP) has been a prevalent method of the study of complexity of these problems since early 2000's. The core of this approach is the notion of polymorphisms which determine the complexity of the problem (up to log-space reductions). In the past few years, a new, more general version of the CSP emerged, the promise constraint satisfaction problem (PCSP), and the notion of polymorphisms and most of the core theses of the algebraic approach were generalised to the promise setting. Nevertheless, recent work also suggests that insights from other fields are immensely useful in the study of PCSPs including algebraic topology. In this paper, we provide an entry point for category-theorists into the study of complexity of CSPs and PCSPs. We show that many standard CSP notions have clear and well-known categorical counterparts. For example, the algebraic structure of polymorphisms can be described as a set-functor defined as a right Kan extension. We provide purely categorical proofs of core results of the algebraic approach including a proof that the complexity only depends on the polymorphisms. Our new proofs are substantially shorter and, from the categorical perspective, cleaner than previous proofs of the same results. Moreover, as expected, they are applicable more widely. We believe that, in particular in the case of PCSPs, category theory brings insights that can help solve some of the current challenges of the field.