A categorical perspective on constraint satisfaction: The wonderland of adjunctions
Maximilian Hadek, Tomáš Jakl, Jakub Opršal · 2025
Read A categorical perspective on constraint satisfaction: The wonderland of adjunctions by Maximilian Hadek, Tomáš Jakl, Jakub Opršal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-10353.txt.
Introduction
Maximilian Hadek, Tomáš Jakl, and Jakub Opršal give category theorists a door into constraint problems in a 2025 paper. Constraint problems ask if set rules can all be met at once, and an algebra approach has led their study since the early 2000s. A newer promise form widens the task.
The trio show that core notions of the field have clean twins in category theory. The algebra of allowed moves, for one, becomes a known functor built by extension. Fresh proofs of core results run shorter and cleaner in this tongue. They also reach wider, which may help most in the promise setting. The paper builds a two-way bridge.
Catalog record
| CREATOR | Maximilian Hadek, Tomáš Jakl, Jakub Opršal |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 103 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-10353
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A categorical perspective on constraint satisfaction: The wonderland of adjunctions Maximilian Hadek, Tomáš Jakl, Jakub Opršal Abstract 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. Charles University, Prague, Czech Republic [email protected] https://orcid.org/0009-0008-2102-7567 Funded by the European Union (ERC Synergy Grant No.101071674, POCOCOP). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. Czech Technical University, Prague, Czech Republic [email protected] https://orcid.org/0000-0003-1930-4904 Partially funded by the EXPRO project 20-31529X awarded by the Czech Science Foundation, and supported by the Institute of Mathematics, Czech Academy of Sciences (RVO 67985840). Also funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101111373. University of Birmingham, Birmingham, UK [email protected] https://orcid.org/0000-0003-1245-3456 In the past, several people have thought about different angles of the categorical perspective on the constraint satisfaction problem. We would like to thank Marcin Wrochna, who has kindly shared his categorical notes on CSPs with us, and Libor Barto for the insights he provided to us over many years. We would like to thank Anuj Dawar for providing funding for Jakub Opršal’s visit to Cambridge in 2022, which initiated the work. keywords constraint satisfaction problem, categorical models and logics ccs Theory of computation Problems, reductions and completeness ccs Theory of computation Finite Model Theory ccs Mathematics of computing † † runningtitle: A categorical perspective on constraint satisfaction † † runningauthor: M. Hadek, T. Jakl, and J. Opršal † † copyright: Maximilian Hadek, Tomáš Jakl, and Jakub Opršal † † related-version: Conference version : https://doi.org/10.4230/LIPIcs.LICS.2026.22 1 Introduction If \textsf{P}\neq\textsf{NP} , what distinguishes problems in P from those that are NP -complete? This question is one of the key motivations for the systematic study of the complexity of constraint satisfaction problems (CSPs) . The goal of a CSP is, given an input instance consisting of variables attaining values in some domain and a list of constraints, each involving a bounded number of variables, to decide whether there exists an assignment of values to variables that satisfies all constraints simultaneously. By varying which constraints are allowed to appear in input instances, we obtain many well-known combinatorial problems including Boolean satisfiability (SAT) and its variants, e.g. HornSAT and 2SAT, graph k -colouring, systems of linear equations over a fixed ring, linear programming, and many others. Formally, the restriction of constraints is given as a single relational structure A called a template . Considerable effort has been dedicated to the complexity classifications of finite-template CSPs (i.e. where the template is a finite relational structure). The most successful theory in addressing the complexity of these problems is the so-called algebraic approach to CSPs . This theory started with the work of Jeavons [ 28 ] , and has been further developed over the past three decades, including the work of Bulatov, Jeavons, and Krokhin [ 12 ] , which gave the theory its current name. The core idea of this theory is to assign to each template A an abstract algebraic structure, denoted by \pol(A) , which determines the complexity of the problem up to log-space reductions. A major achievement of this theory is the CSP Dichotomy Theorem which states that, for each finite structure A , either \plainCSP(A) is NP -complete or it is in P . The statement was first conjectured by Feder and Vardi [ 23 ] and independently confirmed by Bulatov [ 13 ] and Zhuk [ 45 ] . More importantly, the line between NP -complete problems and problems in P is precisely described by the algebraic invariants \pol(A) of the problem, and hence the dichotomy provides a somewhat satisfactory answer to our opening question. In this paper, we revisit the general theory of the algebraic approach through more abstract lenses of category theory; we have two key motivations for this. Firstly, categorical perspectives seem to appear (with or without the knowledge of the authors) more-and-more often in recent work on the complexity of CSPs, and in particular, in the study of the complexity of promise constraint satisfaction problems (PCSPs) . The latter is a natural generalisation of CSPs from decision to promise problems including, e.g. the problem of distinguishing graphs that are 3 -colourable from those that are not even 6 -colourable. Examples of the usage of a categorical language in the PCSP literature include the definition of an abstract minion given by Brakensiek, Guruswami, Wrochna and Živný [ 11 ] , which coincides with the notion of a set functor , or efficient reductions between PCSPs in the form of adjoint functors used by Wrochna and Živný [ 44 , Observations 2.1 and 2.2] . Secondly, a recent direction in the study of PCSPs is based on applying methods from algebraic topology, starting with Krokhin, Opršal, Wrochna, and Živný [ 33 ] and following with Filakovský, Nakajima, Opršal, Tasinato, and Wagner [ 25 ] , Avvakumov, Filakovský, Opršal, Tasinato, and Wagner [ 3 ] , and by Meyer and Opršal [ 36 ] . Since algebraic topology has intimate connections to category theory, a lot of these results already have a clear category-theoretic flavour. Finally, let us also mention that Ó Conghaile [ 37 ] and Abramsky [ 1 ] provided a sheaf-theoretic perspective on k -consistency and similar algorithms. Although categorical thinking is already used in the CSP research, and has led to several key advances, e.g. [ 4 , 33 ] , most authors do not state or explain their results in the categorical language. We believe that a proper categorical exposition is long overdue. This paper is the first step in that direction. CSP notion (used in [ 4 ] ) CT notion Reference minion functor {\text{Fin}}\to{\text{Fin}} [ 11 ] minion homomorphism