A categorical perspective on constraint satisfaction: The wonderland of adjunctions

Jakub Opr\v{s}al; Maximilian Hadek; Tom\'a\v{s} Jakl

arxiv: 2503.10353 · v3 · pith:JEC63BPHnew · submitted 2025-03-13 · 💻 cs.LO · math.CT

A categorical perspective on constraint satisfaction: The wonderland of adjunctions

Maximilian Hadek , Tom\'a\v{s} Jakl , Jakub Opr\v{s}al This is my paper

Pith reviewed 2026-05-23 00:20 UTC · model grok-4.3

classification 💻 cs.LO math.CT

keywords constraint satisfactionpromise constraint satisfactionpolymorphismsright Kan extensionadjunctionscategorical proofscomputational complexityalgebraic approach

0 comments

The pith

The algebraic structure of polymorphisms in constraint satisfaction is a set-functor obtained as a right Kan extension.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper translates the algebraic approach to constraint satisfaction problems into category theory by exhibiting the polymorphisms as a functor constructed via right Kan extension. It then supplies purely categorical proofs of the central theorems, including the claim that problem complexity depends only on the polymorphisms. These proofs are presented as shorter and cleaner than the original algebraic arguments. The reformulation is offered as a route to handling the promise version of the problem.

Core claim

The algebraic structure of polymorphisms can be described as a set-functor defined as a right Kan extension. Purely categorical proofs are given of core results of the algebraic approach, including a proof that the complexity only depends on the polymorphisms. These new proofs are substantially shorter and cleaner than previous proofs of the same results and are applicable more widely.

What carries the argument

The right Kan extension that produces the polymorphism set-functor, which encodes the algebraic information used to classify complexity.

If this is right

The complexity of any CSP instance is completely determined by the associated right Kan extension functor.
All standard results on polymorphisms admit proofs that rely only on the properties of adjunctions and Kan extensions.
The same categorical constructions apply directly to promise constraint satisfaction problems.
Categorical methods can be used to study the tractability of PCSPs where algebraic techniques have been insufficient.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The adjunction perspective may expose structural features of polymorphisms invisible in the purely algebraic treatment.
Category-theoretic tools developed here could be applied to other homomorphism problems that share the same polymorphism structure.
If the categorical proofs generalize cleanly, they may shorten arguments in related areas such as homomorphism duality.

Load-bearing premise

Standard notions such as polymorphisms possess direct categorical counterparts via right Kan extensions and adjunctions that preserve the exact tractability classification.

What would settle it

A concrete CSP template whose complexity class, as computed from its polymorphisms in the usual way, differs from the class predicted by the corresponding right Kan extension functor.

Figures

Figures reproduced from arXiv: 2503.10353 by Jakub Opr\v{s}al, Maximilian Hadek, Tom\'a\v{s} Jakl.

**Figure 1.** Figure 1: Translation table of common constraint satisfaction notions and their category-theoretic counterparts. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

**Figure 2.** Figure 2: Illustration of the left adjoint to the Grothendieck construction. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Figure 3: The setting of Propositions 5.7 and 5.8. of graphs Gra. To specify a functor 𝐺 : Dop → Gra it is enough to select a pair of graphs𝐺(𝑉 ) and𝐺(𝐸) and a pair of homomorphisms 𝐺(𝑠),𝐺(𝑡): 𝐺(𝑉 ) → 𝐺(𝐸). Given such a functor and a multidigraph 𝐴: D → Fin, the graph 𝐺b(𝐴) is constructed by replacing each vertex of 𝐴 by a copy of 𝐺(𝐷) and each edge 𝑒 ∈ 𝐴(𝐸) by a copy of 𝐺(𝐸). These copies are ‘glued’ together accor… view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper recasts polymorphisms as right Kan extensions for shorter categorical proofs but the abstract supplies no derivations to check if the construction stays faithful to the original clone.

read the letter

The paper's main move is to identify the algebraic structure of polymorphisms with a set-functor given by a right Kan extension, then use adjunctions to reprove that CSP complexity depends only on those polymorphisms. This is presented as new to the CSP literature and as yielding substantially shorter, cleaner arguments from a categorical viewpoint, with possible carry-over to PCSPs. That explicit link to standard categorical constructions is the clearest novelty here and could genuinely serve as an entry point for category theorists. It also correctly notes that the algebraic approach has already been extended to the promise setting, so the categorical translation might help there too. The citation pattern looks standard and appropriate. The soft spot is the complete absence of any derivation, example, or verification step in the abstract. Without seeing how the Kan extension is taken and whether it induces a conservative functor on the polymorphism clones, the claim that complexity results transfer directly cannot be assessed. The stress-test worry about extra natural transformations is therefore live until the full text is checked. This work is aimed at people who already know both category theory and the algebraic CSP literature and want to test whether the categorical language simplifies existing proofs. It is worth a serious referee to examine whether the equivalence holds and whether the proofs are actually shorter and correct on the nose.

Referee Report

2 major / 2 minor

Summary. The manuscript develops a categorical framework for the algebraic approach to CSP and PCSP. It identifies standard notions such as polymorphisms with a set-functor obtained as a right Kan extension (along a forgetful functor from a category of templates or relations), models the relevant structure via adjunctions, and supplies purely categorical proofs that CSP complexity depends only on the polymorphisms. The authors claim these proofs are substantially shorter and cleaner than prior algebraic arguments and that the framework extends naturally to promise CSPs.

Significance. If the right Kan extension construction is shown to be faithful (i.e., recovers exactly the standard polymorphism clone without extraneous natural transformations that could alter logspace-reduction classes), the work supplies a new, uniform language for core CSP results and may furnish tools for open PCSP questions. The explicit use of Kan extensions and adjunctions to encode polymorphisms is a clear conceptual contribution; the paper also credits the algebraic approach it re-derives.

major comments (2)

[§4] §4 (the categorical proof that complexity depends only on polymorphisms): The central transfer of the known dichotomy or classification results requires that the right Kan extension functor induces a conservative embedding on polymorphism clones, preserving exact logspace-reduction equivalence classes. The manuscript establishes an embedding but does not supply an explicit verification (e.g., via a commuting diagram or a concrete comparison of the clone of natural transformations with the standard polymorphism clone) that no additional morphisms are adjoined; without this step the transfer of tractability results remains conditional.
[Definition of the polymorphism functor] Definition of the polymorphism functor via right Kan extension (around the statement following the forgetful functor): The claim that this construction is “direct and faithful” is load-bearing for all subsequent results. The text shows that the Kan extension recovers the usual polymorphisms on the nose for concrete templates, but does not address whether the universal property of the Kan extension introduces extra structure when the base category is enlarged to presheaves or when the template category is not skeletal.

minor comments (2)

Notation for the right Kan extension (e.g., the variable naming for the forgetful functor and the presheaf category) is introduced without a consolidated table or diagram; a single diagram collecting all adjunctions and Kan extensions would improve readability.
The abstract asserts “substantially shorter” proofs; the manuscript would benefit from a brief side-by-side length or step-count comparison (even informal) with the corresponding algebraic proofs in the cited references.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and for identifying points where the faithfulness of the Kan extension construction requires additional clarification. We address each major comment below and will revise the manuscript to strengthen the arguments.

read point-by-point responses

Referee: [§4] §4 (the categorical proof that complexity depends only on polymorphisms): The central transfer of the known dichotomy or classification results requires that the right Kan extension functor induces a conservative embedding on polymorphism clones, preserving exact logspace-reduction equivalence classes. The manuscript establishes an embedding but does not supply an explicit verification (e.g., via a commuting diagram or a concrete comparison of the clone of natural transformations with the standard polymorphism clone) that no additional morphisms are adjoined; without this step the transfer of tractability results remains conditional.

Authors: We agree that an explicit verification is needed to confirm that the embedding preserves the exact logspace-reduction equivalence classes without adjoining extraneous morphisms. While the manuscript demonstrates that the right Kan extension recovers the standard polymorphisms for concrete templates, we will add a new lemma in the revised §4. This lemma will include a commuting diagram comparing the clone of natural transformations arising from the Kan extension with the standard polymorphism clone, establishing that they coincide exactly and that the embedding is conservative. revision: yes
Referee: [Definition of the polymorphism functor] Definition of the polymorphism functor via right Kan extension (around the statement following the forgetful functor): The claim that this construction is “direct and faithful” is load-bearing for all subsequent results. The text shows that the Kan extension recovers the usual polymorphisms on the nose for concrete templates, but does not address whether the universal property of the Kan extension introduces extra structure when the base category is enlarged to presheaves or when the template category is not skeletal.

Authors: The polymorphism functor is defined via right Kan extension in the category of sets along the forgetful functor from the category of templates, and the manuscript verifies recovery of standard polymorphisms for the finite, skeletal templates standard in CSP/PCSP. The universal property does not introduce extra natural transformations in this setting because the functor category is taken over Set, where the natural transformations are precisely the polymorphisms. We will add a clarifying remark after the definition to explicitly state the assumptions (finite templates, skeletal category) under which faithfulness holds and note that extensions to presheaf categories lie outside the scope of the current results. revision: partial

Circularity Check

0 steps flagged

Categorical reformulation of CSP via Kan extensions and adjunctions is self-contained with no definitional reduction

full rationale

The paper re-expresses standard CSP notions (polymorphisms, complexity dependence) using right Kan extensions and adjunctions in category theory, then supplies independent categorical proofs of known results. No equations or steps are shown to reduce by construction to fitted parameters, self-definitions, or unverified self-citations; the central claims rest on faithful application of external categorical machinery to pre-existing algebraic CSP concepts rather than deriving the target classification from the construction itself. This matches the default expectation of a non-circular reformulation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper introduces no free parameters, invented entities, or ad-hoc axioms; it relies on the domain assumption that CSP algebraic structures translate faithfully into standard categorical constructions.

axioms (1)

domain assumption CSP notions such as polymorphisms have direct categorical counterparts via right Kan extensions that preserve complexity information
This premise is invoked when the abstract states that polymorphisms can be described as right Kan extensions and that complexity depends only on them.

pith-pipeline@v0.9.0 · 5798 in / 1249 out tokens · 51077 ms · 2026-05-23T00:20:39.043004+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
cs.LO 2026-04 unverdicted novelty 6.0

A minion-theoretic characterization unifies the power of higher-level CSP algorithms and introduces an equivalent Z_p vector relaxation hierarchy that solves the dihedral D4 CSP and modular linear equations.

Reference graph

Works this paper leans on

45 extracted references · 45 canonical work pages · cited by 1 Pith paper

[1]

Samson Abramsky. 2022. Notes on presheaf representations of strategies and cohomological refinements of 𝑘-consistency and 𝑘-equivalence. (2022). doi:10. 48550/ARXIV.2206.12156 arXiv:2206.12156

work page arXiv 2022
[2]

Samson Abramsky and Nikos Tzevelekos. 2010. Introduction to categories and categorical logic. InNew structures for physics. Springer, 3–94

work page 2010
[3]

Sergey Avvakumov, Marek Filakovský, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. 2025. Hardness of 4-Colouring 𝐺-Colourable Graphs. InProceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC ’25). ACM, 72–83. doi:10.1145/3717823.3718154

work page doi:10.1145/3717823.3718154 2025
[4]

Libor Barto, Jakub Bulín, Andrei Krokhin, and Jakub Opršal. 2021. Algebraic Approach to Promise Constraint Satisfaction.J. ACM68, 4 (8 2021), 28:1–66. doi:10.1145/3457606

work page doi:10.1145/3457606 2021
[5]

Libor Barto, Silvia Butti, Alexandr Kazda, Caterina Viola, and Stanislav Živný

work page
[6]

Delooping cyclic groups with lens spaces in homotopy type theory

Algebraic Approach to Approximation. InProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2024(Tallinn, Estonia, July 8-11, 2024). ACM, 10:1–10:14. doi:10.1145/3661814.3662076

work page doi:10.1145/3661814.3662076 2024
[7]

Libor Barto, William DeMeo, and Antoine Mottet. 2021. Constraint Satisfaction Problems over Finite Structures. In2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE, 1–13. doi:10.1109/lics52264.2021.9470670

work page doi:10.1109/lics52264.2021.9470670 2021
[8]

Libor Barto, Andrei Krokhin, and Ross Willard. 2017. Polymorphisms, and How to Use Them. InThe Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav Živný (Eds.). Dagstuhl Follow- Ups, Vol. 7. Schloss Dagstuhl – LZI, Dagstuhl, Germany, 1–44. doi:10.4230/DFU. Vol7.15301.1

work page doi:10.4230/dfu 2017
[9]

Libor Barto and Antoine Mottet. 2024. Finite algebras with Hom-sets of polyno- mial size.Trans. Amer. Math. Soc.(Sept. 2024). doi:10.1090/tran/9262

work page doi:10.1090/tran/9262 2024
[10]

Libor Barto, Jakub Opršal, and Michael Pinsker. 2018. The wonderland of reflec- tions.Israel Journal of Mathematics223, 1 (2018), 363–398

work page 2018
[11]

Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Živný. 2020. The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems.SIAM J. Comput.49, 6 (2020), 1232–1248. doi:10.1137/20M1312745 Maximilian Hadek, Tomáš Jakl, and Jakub Opršal

work page doi:10.1137/20m1312745 2020
[12]

Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. 2005. Classifying the Com- plexity of Constraints Using Finite Algebras.SIAM J. Comput.34, 3 (2005), 720–742. doi:10.1137/S0097539700376676

work page doi:10.1137/s0097539700376676 2005
[13]

Andrei A. Bulatov. 2017. A Dichotomy Theorem for Nonuniform CSPs. In2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, Berkeley, CA, USA, 319–330. doi:10.1109/FOCS.2017.37

work page doi:10.1109/focs.2017.37 2017
[14]

Bulatov and Peter Jeavons

Andrei A. Bulatov and Peter Jeavons. 2003. An Algebraic Approach to Multi- sorted Constraints. InPrinciples and Practice of Constraint Programming - CP 2003, 9th International Conference, CP 2003, Kinsale, Ireland, September 29 - October 3, 2003, Proceedings (Lecture Notes in Computer Science, Vol. 2833), Francesca Rossi (Ed.). Springer, 183–198. doi:10.1...

work page doi:10.1007/978-3-540-45193-8_13 2003
[15]

Siu On Chan and Hiu Tsun Ng. 2025. How Random CSPs Fool Hierarchies: II. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, Michal Koucký and Nikhil Bansal (Eds.). ACM, 1710–1721. doi:10.1145/3717823.3718301

work page doi:10.1145/3717823.3718301 2025
[16]

Siu On Chan, Hiu Tsun Ng, and Sijin Peng. 2024. How Random CSPs Fool Hierarchies. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, Bojan Mohar, Igor Shinkar, and Ryan O’Donnell (Eds.). ACM, 1944–1955. doi:10.1145/3618260. 3649613

work page doi:10.1145/3618260 2024
[17]

Ashok K Chandra and Philip M Merlin. 1977. Optimal implementation of con- junctive queries in relational data bases. InProceedings of the ninth annual ACM symposium on Theory of computing. 77–90

work page 1977
[18]

Lorenzo Ciardo and Stanislav Zivný. 2025. Approximate Graph Coloring and the Crystal with a Hollow Shadow.SIAM J. Comput.54, 4 (2025), 1138–1192. doi:10.1137/24M1691594

work page doi:10.1137/24m1691594 2025
[19]

Jonas Conneryd, Yassine Ghannane, and Shuo Pang. 2025. Lower Bounds for CSP Hierarchies Through Ideal Reduction.CoRRabs/2511.17272 (2025). doi:10. 48550/ARXIV.2511.17272 arXiv:2511.17272 To appear at SODA 2026

work page arXiv 2025
[20]

Víctor Dalmau, Andrei Krokhin, and Jakub Opršal. 2024. Functors on Relational Structures Which Admit Both Left and Right Adjoints.SIAM J. Discret. Math.38, 3 (2024), 2041–2068. doi:10.1137/23M1555223

work page doi:10.1137/23m1555223 2024
[21]

Víctor Dalmau and Jakub Opršal. 2024. Local consistency as a reduction between constraint satisfaction problems. In39th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS ’24)(Tallinn, Estonia, July 8–11, 2024). ACM, New York, NY, USA, 15 pages. doi:10.1145/3661814.3662068

work page doi:10.1145/3661814.3662068 2024
[22]

2025.Theory of Computing21, 1 (2025), 1–50

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. 2025.Theory of Computing21, 1 (2025), 1–50. doi:10.4086/toc.2025.v021a011

work page doi:10.4086/toc.2025.v021a011 2025
[23]

Tomás Feder, Florent Madelaine, and Iain A. Stewart. 2004. Dichotomies for classes of homomorphism problems involving unary functions.Theoretical Computer Science314, 1–2 (Feb. 2004), 1–43. doi:10.1016/j.tcs.2003.12.015

work page doi:10.1016/j.tcs.2003.12.015 2004
[24]

Tomás Feder and Moshe Y. Vardi. 1998. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory.SIAM J. Comput.28, 1 (1998), 57–104

work page 1998
[25]

Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. 2024. Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs. In41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024(Clermont-Ferrand, France, March 12–14, 2024) (LIPIcs, Vol. 289). Schloss Dagstuhl – Leibniz-Zentr...

work page doi:10.4230/lipics.stacs.2024.34 2024
[26]

Pavol Hell and Jaroslav Nešetřil. 1990. On the complexity of𝐻-coloring.J. Comb. Theory B48, 1 (1990), 92–110. doi:10.1016/0095-8956(90)90132-J

work page doi:10.1016/0095-8956(90)90132-j 1990
[27]

Peter Jeavons. 1998. On the algebraic structure of combinatorial problems. Theoretical Computer Science200, 1-2 (1998), 185–204

work page 1998
[28]

Daniel M. Kan. 1958. Functors Involving C.S.S. Complexes.Trans. Amer. Math. Soc.87, 2 (1958), 330–346. http://www.jstor.org/stable/1993103

work page arXiv 1958
[29]

G.M. Kelly. 1982.Basic concepts of enriched category theory. Cambridge University Press, New York. 245 pages

work page 1982
[30]

Subhash Khot. 2002. On the power of unique 2-prover 1-round games. InProceed- ings of the thiry-fourth annual ACM symposium on Theory of computing (STOC02). ACM, 767–775. doi:10.1145/509907.510017

work page doi:10.1145/509907.510017 2002
[31]

Andrei Krokhin and Jakub Opršal. 2022. An invitation to the promise constraint satisfaction problem.ACM SIGLOG News9, 3 (2022), 30–59. doi:10.1145/3559736. 3559740 arXiv:2208.13538

work page doi:10.1145/3559736 2022
[32]

Krokhin, Jakub Opršal, Marcin Wrochna, and Stanislav Živný

Andrei A. Krokhin, Jakub Opršal, Marcin Wrochna, and Stanislav Živný. 2023. Topology and adjunction in promise constraint satisfaction.SIAM J. Comput.52, 1 (2023), 38–79. doi:10.1137/20M1378223 arXiv:2003.11351

work page doi:10.1137/20m1378223 2023
[33]

Moritz Lichter and Benedikt Pago. 2025. Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems. In52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, Aarhus, Denmark, July 8-11, 2025 (LIPIcs, Vol. 334), Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis (Eds.). Schloss ...

work page doi:10.4230/lipics.icalp.2025.166 2025
[34]

Anatolii Ivanovich Maltsev. 1954. On the general theory of algebraic systems. Matematicheskii sbornik77, 1 (1954), 3–20

work page 1954
[35]

Sebastian Meyer and Jakub Opršal. 2025. A topological proof of the Hell–Nešetřil dichotomy. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025). Society for Industrial and Applied Mathematics, 4507–

work page 2025
[36]

doi:10.1137/1.9781611978322.154 arXiv:2409.12627

work page doi:10.1137/1.9781611978322.154
[37]

Adam Ó Conghaile. 2022. Cohomology in Constraint Satisfaction and Structure Isomorphism. In47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 241), Stefan Szeider, Robert Ganian, and Alexandra Silva (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informat...

work page doi:10.4230/lipics.mfcs.2022.75 2022
[38]

Miroslav Olšák. 2019. Loop conditions.Algebra universalis81, 1 (Nov. 2019). doi:10.1007/s00012-019-0631-3

work page doi:10.1007/s00012-019-0631-3 2019
[39]

1990.Accessible Categories: The Foundations of Categorical Model Theory

Robert Paré and Michael Makkai. 1990.Accessible Categories: The Foundations of Categorical Model Theory. Contemporary Mathematics, Vol. 104. AMS. 176 pages

work page 1990
[40]

Aleš Pultr. 1970. The right adjoints into the categories of relational systems. InReports of the Midwest Category Seminar IV (Lecture Notes in Mathematics, Vol. 137). Springer, 100–113. doi:10.1007/BFb0060437

work page doi:10.1007/bfb0060437 1970
[41]

Omer Reingold. 2008. Undirected Connectivity in Log-space.J. ACM55, 4 (2008), 17:1–17:24. doi:10.1145/1391289.1391291

work page doi:10.1145/1391289.1391291 2008
[42]

2016.Category Theory in Context

Emily Riehl. 2016.Category Theory in Context. Dover Publications, Mineola, New York

work page 2016
[43]

Mark H. Siggers. 2010. A New Proof of the 𝐻-Coloring Dichotomy.SIAM J. Discret. Math.23, 4 (2010), 2204–2210. doi:10.1137/080736697

work page doi:10.1137/080736697 2010
[44]

Marcin Wrochna and Stanislav Živný. 2019. Improved hardness for H-colourings of G-colourable graphs. arXiv:1907.00872v3 [cs.CC] A full version of the article with the same name, published at the Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’20), pages 1426–1435, 2020

work page arXiv 2019
[45]

Dmitriy Zhuk. 2020. A Proof of the CSP Dichotomy Conjecture.J. ACM67, 5 (2020), 30:1–30:78. doi:10.1145/3402029 A Logical formulation of CSPs There is a third possible formulation of a CSP which we have not discussed in the main part of the paper. Namely, viewing the CSP with templateA, which is a relational structure, as the problem of satisfaction of pr...

work page doi:10.1145/3402029 2020

[1] [1]

Samson Abramsky. 2022. Notes on presheaf representations of strategies and cohomological refinements of 𝑘-consistency and 𝑘-equivalence. (2022). doi:10. 48550/ARXIV.2206.12156 arXiv:2206.12156

work page arXiv 2022

[2] [2]

Samson Abramsky and Nikos Tzevelekos. 2010. Introduction to categories and categorical logic. InNew structures for physics. Springer, 3–94

work page 2010

[3] [3]

Sergey Avvakumov, Marek Filakovský, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. 2025. Hardness of 4-Colouring 𝐺-Colourable Graphs. InProceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC ’25). ACM, 72–83. doi:10.1145/3717823.3718154

work page doi:10.1145/3717823.3718154 2025

[4] [4]

Libor Barto, Jakub Bulín, Andrei Krokhin, and Jakub Opršal. 2021. Algebraic Approach to Promise Constraint Satisfaction.J. ACM68, 4 (8 2021), 28:1–66. doi:10.1145/3457606

work page doi:10.1145/3457606 2021

[5] [5]

Libor Barto, Silvia Butti, Alexandr Kazda, Caterina Viola, and Stanislav Živný

work page

[6] [6]

Delooping cyclic groups with lens spaces in homotopy type theory

Algebraic Approach to Approximation. InProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2024(Tallinn, Estonia, July 8-11, 2024). ACM, 10:1–10:14. doi:10.1145/3661814.3662076

work page doi:10.1145/3661814.3662076 2024

[7] [7]

Libor Barto, William DeMeo, and Antoine Mottet. 2021. Constraint Satisfaction Problems over Finite Structures. In2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE, 1–13. doi:10.1109/lics52264.2021.9470670

work page doi:10.1109/lics52264.2021.9470670 2021

[8] [8]

Libor Barto, Andrei Krokhin, and Ross Willard. 2017. Polymorphisms, and How to Use Them. InThe Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav Živný (Eds.). Dagstuhl Follow- Ups, Vol. 7. Schloss Dagstuhl – LZI, Dagstuhl, Germany, 1–44. doi:10.4230/DFU. Vol7.15301.1

work page doi:10.4230/dfu 2017

[9] [9]

Libor Barto and Antoine Mottet. 2024. Finite algebras with Hom-sets of polyno- mial size.Trans. Amer. Math. Soc.(Sept. 2024). doi:10.1090/tran/9262

work page doi:10.1090/tran/9262 2024

[10] [10]

Libor Barto, Jakub Opršal, and Michael Pinsker. 2018. The wonderland of reflec- tions.Israel Journal of Mathematics223, 1 (2018), 363–398

work page 2018

[11] [11]

Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Živný. 2020. The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems.SIAM J. Comput.49, 6 (2020), 1232–1248. doi:10.1137/20M1312745 Maximilian Hadek, Tomáš Jakl, and Jakub Opršal

work page doi:10.1137/20m1312745 2020

[12] [12]

Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. 2005. Classifying the Com- plexity of Constraints Using Finite Algebras.SIAM J. Comput.34, 3 (2005), 720–742. doi:10.1137/S0097539700376676

work page doi:10.1137/s0097539700376676 2005

[13] [13]

Andrei A. Bulatov. 2017. A Dichotomy Theorem for Nonuniform CSPs. In2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, Berkeley, CA, USA, 319–330. doi:10.1109/FOCS.2017.37

work page doi:10.1109/focs.2017.37 2017

[14] [14]

Bulatov and Peter Jeavons

Andrei A. Bulatov and Peter Jeavons. 2003. An Algebraic Approach to Multi- sorted Constraints. InPrinciples and Practice of Constraint Programming - CP 2003, 9th International Conference, CP 2003, Kinsale, Ireland, September 29 - October 3, 2003, Proceedings (Lecture Notes in Computer Science, Vol. 2833), Francesca Rossi (Ed.). Springer, 183–198. doi:10.1...

work page doi:10.1007/978-3-540-45193-8_13 2003

[15] [15]

Siu On Chan and Hiu Tsun Ng. 2025. How Random CSPs Fool Hierarchies: II. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, Michal Koucký and Nikhil Bansal (Eds.). ACM, 1710–1721. doi:10.1145/3717823.3718301

work page doi:10.1145/3717823.3718301 2025

[16] [16]

Siu On Chan, Hiu Tsun Ng, and Sijin Peng. 2024. How Random CSPs Fool Hierarchies. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, Bojan Mohar, Igor Shinkar, and Ryan O’Donnell (Eds.). ACM, 1944–1955. doi:10.1145/3618260. 3649613

work page doi:10.1145/3618260 2024

[17] [17]

Ashok K Chandra and Philip M Merlin. 1977. Optimal implementation of con- junctive queries in relational data bases. InProceedings of the ninth annual ACM symposium on Theory of computing. 77–90

work page 1977

[18] [18]

Lorenzo Ciardo and Stanislav Zivný. 2025. Approximate Graph Coloring and the Crystal with a Hollow Shadow.SIAM J. Comput.54, 4 (2025), 1138–1192. doi:10.1137/24M1691594

work page doi:10.1137/24m1691594 2025

[19] [19]

Jonas Conneryd, Yassine Ghannane, and Shuo Pang. 2025. Lower Bounds for CSP Hierarchies Through Ideal Reduction.CoRRabs/2511.17272 (2025). doi:10. 48550/ARXIV.2511.17272 arXiv:2511.17272 To appear at SODA 2026

work page arXiv 2025

[20] [20]

Víctor Dalmau, Andrei Krokhin, and Jakub Opršal. 2024. Functors on Relational Structures Which Admit Both Left and Right Adjoints.SIAM J. Discret. Math.38, 3 (2024), 2041–2068. doi:10.1137/23M1555223

work page doi:10.1137/23m1555223 2024

[21] [21]

Víctor Dalmau and Jakub Opršal. 2024. Local consistency as a reduction between constraint satisfaction problems. In39th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS ’24)(Tallinn, Estonia, July 8–11, 2024). ACM, New York, NY, USA, 15 pages. doi:10.1145/3661814.3662068

work page doi:10.1145/3661814.3662068 2024

[22] [22]

2025.Theory of Computing21, 1 (2025), 1–50

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. 2025.Theory of Computing21, 1 (2025), 1–50. doi:10.4086/toc.2025.v021a011

work page doi:10.4086/toc.2025.v021a011 2025

[23] [23]

Tomás Feder, Florent Madelaine, and Iain A. Stewart. 2004. Dichotomies for classes of homomorphism problems involving unary functions.Theoretical Computer Science314, 1–2 (Feb. 2004), 1–43. doi:10.1016/j.tcs.2003.12.015

work page doi:10.1016/j.tcs.2003.12.015 2004

[24] [24]

Tomás Feder and Moshe Y. Vardi. 1998. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory.SIAM J. Comput.28, 1 (1998), 57–104

work page 1998

[25] [25]

Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. 2024. Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs. In41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024(Clermont-Ferrand, France, March 12–14, 2024) (LIPIcs, Vol. 289). Schloss Dagstuhl – Leibniz-Zentr...

work page doi:10.4230/lipics.stacs.2024.34 2024

[26] [26]

Pavol Hell and Jaroslav Nešetřil. 1990. On the complexity of𝐻-coloring.J. Comb. Theory B48, 1 (1990), 92–110. doi:10.1016/0095-8956(90)90132-J

work page doi:10.1016/0095-8956(90)90132-j 1990

[27] [27]

Peter Jeavons. 1998. On the algebraic structure of combinatorial problems. Theoretical Computer Science200, 1-2 (1998), 185–204

work page 1998

[28] [28]

Daniel M. Kan. 1958. Functors Involving C.S.S. Complexes.Trans. Amer. Math. Soc.87, 2 (1958), 330–346. http://www.jstor.org/stable/1993103

work page arXiv 1958

[29] [29]

G.M. Kelly. 1982.Basic concepts of enriched category theory. Cambridge University Press, New York. 245 pages

work page 1982

[30] [30]

Subhash Khot. 2002. On the power of unique 2-prover 1-round games. InProceed- ings of the thiry-fourth annual ACM symposium on Theory of computing (STOC02). ACM, 767–775. doi:10.1145/509907.510017

work page doi:10.1145/509907.510017 2002

[31] [31]

Andrei Krokhin and Jakub Opršal. 2022. An invitation to the promise constraint satisfaction problem.ACM SIGLOG News9, 3 (2022), 30–59. doi:10.1145/3559736. 3559740 arXiv:2208.13538

work page doi:10.1145/3559736 2022

[32] [32]

Krokhin, Jakub Opršal, Marcin Wrochna, and Stanislav Živný

Andrei A. Krokhin, Jakub Opršal, Marcin Wrochna, and Stanislav Živný. 2023. Topology and adjunction in promise constraint satisfaction.SIAM J. Comput.52, 1 (2023), 38–79. doi:10.1137/20M1378223 arXiv:2003.11351

work page doi:10.1137/20m1378223 2023

[33] [33]

Moritz Lichter and Benedikt Pago. 2025. Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems. In52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, Aarhus, Denmark, July 8-11, 2025 (LIPIcs, Vol. 334), Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis (Eds.). Schloss ...

work page doi:10.4230/lipics.icalp.2025.166 2025

[34] [34]

Anatolii Ivanovich Maltsev. 1954. On the general theory of algebraic systems. Matematicheskii sbornik77, 1 (1954), 3–20

work page 1954

[35] [35]

Sebastian Meyer and Jakub Opršal. 2025. A topological proof of the Hell–Nešetřil dichotomy. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025). Society for Industrial and Applied Mathematics, 4507–

work page 2025

[36] [36]

doi:10.1137/1.9781611978322.154 arXiv:2409.12627

work page doi:10.1137/1.9781611978322.154

[37] [37]

Adam Ó Conghaile. 2022. Cohomology in Constraint Satisfaction and Structure Isomorphism. In47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 241), Stefan Szeider, Robert Ganian, and Alexandra Silva (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informat...

work page doi:10.4230/lipics.mfcs.2022.75 2022

[38] [38]

Miroslav Olšák. 2019. Loop conditions.Algebra universalis81, 1 (Nov. 2019). doi:10.1007/s00012-019-0631-3

work page doi:10.1007/s00012-019-0631-3 2019

[39] [39]

1990.Accessible Categories: The Foundations of Categorical Model Theory

Robert Paré and Michael Makkai. 1990.Accessible Categories: The Foundations of Categorical Model Theory. Contemporary Mathematics, Vol. 104. AMS. 176 pages

work page 1990

[40] [40]

Aleš Pultr. 1970. The right adjoints into the categories of relational systems. InReports of the Midwest Category Seminar IV (Lecture Notes in Mathematics, Vol. 137). Springer, 100–113. doi:10.1007/BFb0060437

work page doi:10.1007/bfb0060437 1970

[41] [41]

Omer Reingold. 2008. Undirected Connectivity in Log-space.J. ACM55, 4 (2008), 17:1–17:24. doi:10.1145/1391289.1391291

work page doi:10.1145/1391289.1391291 2008

[42] [42]

2016.Category Theory in Context

Emily Riehl. 2016.Category Theory in Context. Dover Publications, Mineola, New York

work page 2016

[43] [43]

Mark H. Siggers. 2010. A New Proof of the 𝐻-Coloring Dichotomy.SIAM J. Discret. Math.23, 4 (2010), 2204–2210. doi:10.1137/080736697

work page doi:10.1137/080736697 2010

[44] [44]

Marcin Wrochna and Stanislav Živný. 2019. Improved hardness for H-colourings of G-colourable graphs. arXiv:1907.00872v3 [cs.CC] A full version of the article with the same name, published at the Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’20), pages 1426–1435, 2020

work page arXiv 2019

[45] [45]

Dmitriy Zhuk. 2020. A Proof of the CSP Dichotomy Conjecture.J. ACM67, 5 (2020), 30:1–30:78. doi:10.1145/3402029 A Logical formulation of CSPs There is a third possible formulation of a CSP which we have not discussed in the main part of the paper. Namely, viewing the CSP with templateA, which is a relational structure, as the problem of satisfaction of pr...

work page doi:10.1145/3402029 2020