Pith. sign in

REVIEW 2 major objections 5 minor 64 references

The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms

T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that the network satisfaction problem of every finite relation algebra with at most four atoms is either in polynomial time or NP-hard, and it determines the representation type of each of the 102 four-atom integral…

desk verdict Genuine boundary-crossing classification: full NSP dichotomy for four-atom relation algebras with new hardness and tractability techniques; the main caveat is unshipped computer verifications behind two classification claims. read the letter →

arxiv 2507.09324 v2 pith:FCVUWG67 submitted 2025-07-12 math.RA cs.CCmath.LO

Manuel Bodirsky , Moritz Jahn , Simon Knäuer , Matěj Konečný , Paul Winkler This is my paper · ORCID
classification math.RAcs.CCmath.LO MSC 03G1568Q25
keywords networksatisfactionproblemrelationalgebraNP-hardnessdichotomyconstraintnormalrepresentationfullyuniversalatomstructurepolynomial-timealgorithm
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves a dichotomy for the network satisfaction problem of relation algebras with at most four atoms: every such problem is either solvable in polynomial time or NP-hard, with no intermediate complexity. A network satisfaction problem asks whether a finite set of binary constraints, labelled by the algebra's elements, can be realised in some representation of the algebra. The proof extends the earlier three-atom classification and rests on a complete census of the 102 integral four-atom algebras, deciding for each whether it is representable and whether the representation can be chosen normal, fully universal, bounded square, or not at all. It also confirms the tractability conjecture stated in the introduction for every normal representation in the list. Along the way the paper introduces new hardness reductions from a promise graph-colouring problem and new polynomial-time divide-and-conquer algorithms for concrete algebras.

What carries the argument

The central object is the network satisfaction problem NSP(A) for a finite relation algebra A, and the argument is organized around a hierarchy of representation types: normal, fully universal square, fully universal, bounded square, and non-representable. The load-bearing mechanism is the census of all integral relation algebras with at most four atoms, matched against transfer theorems that convert representation type into complexity: Theorem 2.39 characterizes normal representability by an amalgamation property of consistent atomic networks, Corollary 2.41 characterizes fully universal square representability by the same property together with joint embedding, and Lemma 3.4 turns bounded square representations into NP-completeness. Hardness is propagated through the 2-cycle product construction, primitive-positive interpretations, and a reduction from a promise graph-coloring problem; tractability is obtained by path consistency, by polynomial-time algorithms on the atom structure, and by new divide-and-conquer procedures for two of the algebras.

What would settle it

Re-run the two finite checks independently and compare: for each algebra claimed to have a normal representation, verify the amalgamation condition of Theorem 2.39 by hand or with a certified program, and for each atom structure claimed to have an NP-complete CSP, verify the absence of the binary symmetric, majority, or minority polymorphism required by Theorem 2.11; a single algebra failing its claimed condition would overturn the classification, as would a four-atom algebra whose network satisfaction problem is provably neither in P nor NP-hard.

Watch

Extended reading notes

Core claim

The central discovery is that the dichotomy between polynomial-time solvability and NP-hardness holds for the network satisfaction problem of every finite relation algebra with at most four atoms. Along the way the paper gives a complete census of the 102 integral four-atom algebras, deciding for each whether it is representable and, if so, whether the representation can be chosen normal (square, fully universal, and homogeneous), fully universal square, fully universal, or of bounded square size. Representable algebras with bounded square size get NP-complete NSP by a guessing argument; normal and fully universal cases are dispatched by existing criteria; the residual cases are settled by gadget reductions, including a reduction from the promise problem of deciding whether a graph is 3-colorable or not even 5-colorable. For normal representations, the paper confirms the tractability conjecture stated in its introduction: whenever the representation does not primitive-positively construct the Boolean not-all-equal relation, the problem is in P. It also shows that the NSP of every algebra in the list except 56 65 is in NP, with the exceptional case covered by a separate publication.

Load-bearing premise

The classification depends on two computer verifications that are described but not supplied with code, data, or certificates: the check of the normal-representability condition of Theorem 2.39 for the algebras listed in (4.1), and the check of the atom-structure polymorphism conditions reported in Remark 6.11; an error in either would undermine the lists of representations and the complexity labels built on them.

Editorial extensions

If this is right

  • Every relation algebra with at most four atoms has an NSP that is either polynomial-time solvable or NP-hard, so no Ladner-style intermediate complexity appears in this family.
  • For every normal representation in the classification, failure to pp-construct the not-all-equal relation implies polynomial-time solvability, confirming the paper's tractability conjecture on this class.
  • Of the 102 integral four-atom algebras, 31 are non-representable and the remaining 71 are representable, with their representation type (normal, fully universal square, fully universal, or bounded square) determined.
  • Several previously unclassified algebras receive explicit polynomial-time algorithms, including the 3-edge-coloured clique algebra 24 65 and the quasi-transitive orientation algebra 17 37.
  • The NSP of every algebra in the list except 56 65 is shown to be in NP; the remaining case is covered by a separate paper cited in the text.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The two computer checks described in Section 4.3 and Remark 6.11 are the natural targets for independent certification; producing machine-checkable certificates for them would turn the classification into a fully verified result.
  • The reduction template of Proposition 5.26—two symmetric atoms p and q with (p,p,p) and (q,q,q) forbidden and (p,q,q) allowed—gives a table-lookable sufficient condition for NP-hardness that is likely to transfer to algebras with more atoms.
  • The paper's remark that five-atom algebras already number in the thousands suggests that a direct extension will require automated amalgamation checks with independently verifiable certificates, rather than the handwritten case analysis used here.
  • For fully universal representations, the NSP coincides with the CSP of the atom structure, so the boundary between P and NP-hard in this family coincides with the presence or absence of a binary symmetric, majority, or minority polymorphism on the atom structure; that reformulation may guide searches among larger algebras.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper extends the Andreka-Maddux classification of relation algebras with at most three atoms and the Hirsch-Cristiani complexity dichotomy to all finite relation algebras with at most four atoms. The main result, Theorem 1.4, states that for every such algebra A the network satisfaction problem NSP(A) is either in P or NP-hard. The proof proceeds by reducing to simple integral algebras, using Maddux's exhaustive lists, and then classifying each algebra according to whether it has a normal, fully universal, bounded-square, or merely universal representation. Polynomial-time algorithms are given for the tractable cases, including divide-and-conquer algorithms for 24_65 and 17_37, and NP-hardness is proved by a variety of methods, including reductions from promise CSPs such as PCSP(K3,K5). The paper also proves Theorem 1.5, confirming the Bodirsky-Pinsker tractability conjecture for the normal representations of these algebras.

Significance. If the classification is correct, this is a substantial step beyond the three-atom case and provides a rich testbed for the infinite-domain CSP programme. The paper contains several original and reusable technical contributions: the combinatorial characterization of fully universal square representations, the use of promise CSP hardness for network satisfaction problems, the explicit representations for 51_65, 56_65, 39_65 and 62_65, and the polynomial-time algorithms for 24_65 and 17_37. The detailed tables (Tables 4 and 5) are valuable as a reference. However, the exhaustive character of the main theorem depends on two computer verifications that are not supplied to the reader, and the paper itself flags one of them as without proof. This reproducibility gap is the main obstacle to accepting the paper in its present form.

major comments (2)
  1. [Section 4.3, list (4.1) and Figure 7] The classification of which at-most-four-atom algebras have normal representations is load-bearing for Theorem 1.4, but it is justified by the sentence 'we verified the condition in all cases by a computer program,' with no program, source code, data, or certificates supplied. Later arguments that apply only to algebras with normal representations (e.g., Theorems 5.8 and 5.10 and Propositions 5.16-5.21) inherit this classification. The counterexample rows in Figure 7 are also asserted without a displayed verification for each row. I request either a reproducible artifact (program plus output or certificates) or complete hand-verifiable proofs for the inclusions in (4.1) and for each of the fifteen counterexample rows in Figure 7.
  2. [Remark 6.11] The paper states, 'We mention (without proof) that the CSP of the atom structure of every relation algebra with at most four atoms not mentioned in this section is NP-complete. To check this we used a computer program to verify the conditions given in Theorem 2.11.' No proof, program, or certificates are provided. The displayed hardness proofs in Section 5 do not appear to invoke this remark, but the remark is presented as an exhaustive classification fact and should be either proved, removed, or accompanied by a reproducible verification; otherwise the reader cannot determine whether the atom-structure tractability arguments are complete.
minor comments (5)
  1. [Section 5.6, Proposition 5.17] In the displayed pp-formula, the atom 'x4' appears in the conjunct '(r union Id)(z2,x4)', but x4 is not quantified and does not occur in the gadget description; this is presumably a typo for 'z4' (or the quantifier list should be amended).
  2. [Section 4.6, Propositions 4.13 and 4.14] The assertions that 39_65 fails AP(3,2,4) and 62_65 fails AP(3,2,6) are justified only by pointing to a figure. For reproducibility, please state explicitly which amalgamation instances fail and verify that the displayed labels respect the allowed triples.
  3. [Section 4.7.3, Proposition 4.26] The proof of representability of 56_65 verifies only the composition b composed with b equals a union b union Id and says the other cases are very similar. Since this representation is used in Corollary 5.27, I recommend including a complete composition table or an appendix with the remaining cases.
  4. [Remark 4.4] The claim that 62_65 has AP(5) but not AP(6), and that it is the unique four-atom algebra with this behavior, is stated without proof. If this remark is only about the optimality of Theorem 2.39, please label it as such; if it is used in the classification, a proof is needed.
  5. [Tables 4 and 5, row for 56_65] The table lists NSP(56_65) as NP-complete, citing the unpublished preprint [BGPJ+25] for containment in NP. Since Theorem 1.4 only asserts NP-hardness for this case, the table should clearly mark the NP-completeness entry as relying on an external preprint, or the proof should be included.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity in the derivation; unshipped computer checks and self-citations are verification concerns, not circular reductions.

full rationale

The paper's classification is built on Maddux's exhaustive lists, the representability results for small relation algebras, independent NP-hardness sources (SAT, graph coloring, PCSP(K3,K5)), and published theorems such as Bulatov's conservative CSP dichotomy. The derivation chain never assumes NSP(A) tractability or hardness in order to prove itself. Self-citations to [BK20], [BK22], [BK23], and [Bod18] are external, published, parameter-free theorems with stated assumptions that do not contain the target result, so they count as independent support rather than circularity. The computer-assisted verifications mentioned in Section 4.3 and Remark 6.11 are not supplied as code or certificates, but they are checks of external criteria (Theorem 2.39 and Theorem 2.11), not fitted parameters or definitions in terms of the conclusion; a wrong verification would be a correctness or reproducibility flaw, not a circular one. I therefore find no step where an equation is equivalent to its input by construction, no fitted parameter is renamed as a prediction, and no load-bearing claim reduces to an unverified self-citation.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The classification rests on published enumerations and on two unshipped computer verifications. No free parameters or invented entities appear. The main external inputs are Maddux's list of integral four-atom algebras, the three-atom classification, and standard theorems from model theory, universal algebra, and complexity theory.

assumptions (6)
  • domain assumption Maddux's enumeration of the 102 integral relation algebras with four atoms is complete and correct
    The classification and all tables build on the exhaustive list in [Mad06b]; a missing or mis-described algebra would invalidate Theorem 1.4.
  • domain assumption The classification of relation algebras with at most three atoms by Andráska and Maddux is correct
    Used as the base case and in 2-cycle product decompositions in Section 4.4.
  • domain assumption The NSP complexity classification for at most three atoms from Cristiani-Hirsch [CH04] with corrections in [BK20] is correct
    The dichotomy for four atoms extends this classification and uses it in hardness and tractability arguments.
  • ad hoc to paper The computer program used to verify the normal-representation condition in Section 4.3 is bug-free
    The list (4.1) of normal-representable algebras is asserted after a computer verification, with no code or output provided.
  • ad hoc to paper The computer program referenced in Remark 6.11 for checking atom-structure NP-completeness is bug-free
    The claim that all remaining atom structures have NP-complete CSPs is stated without proof and only via an unprovided program.
  • standard math Standard model-theoretic, combinatorics, and complexity theorems used here are correct
    Includes Fraïssé's theorem, amalgamation characterizations in Theorem 2.39 and 2.40, Ramsey's theorem, Post's lattice, Schaefer's theorem, and Bulatov's conservative CSP dichotomy.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms." pith.science (2026). https://pith.science/paper/FCVUWG67

@misc{pith2026250709324,
  author       = {Pith},
  title        = {Pith review of: The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FCVUWG67}},
  note         = {Machine review of arXiv:2507.09324}
}
read the original abstract

Andr\'eka and Maddux classified the relation algebras with at most 3 atoms, and in particular they showed that all of them are representable. Hirsch and Cristiani showed that the network satisfaction problem (NSP) for each of these algebras is in P or NP-hard. The literature contains many results on representations of relation algebras; in particular, some relation algebras with four atoms are not representable. We extend the result of Cristiani and Hirsch to relation algebras with at most 4 atoms: the NSP is always either in P or NP-hard. To this end, we construct universal, fully universal, or even normal representations for these algebras, whenever possible.

Figures

Figures reproduced from arXiv: 2507.09324 by the authors.

Figure 1
Figure 1. Multiplication table of the simple non-integral relation algebra from Example [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. The evil square; it plays an important role in various proofs that certain relation algebras, e.g., 57, do not have a fully universal square representation. (Throughout the paper, we will represent symmetric relations by undirected edges.) 2.5 Networks If A is a relation algebra, then an A-network (V, f) consists of a finite set of variables V and a function f : V 2 → A (see, e.g., [Bod21, Section 1.5.3]). If B is a… view at source ↗
Figure 3
Figure 3. A representation of 1765 = 22[57] is given by Z a,c 5 [Kb ω]. Lemma 3.1 ([BK23, Lemma 2.10]). Let A and B be finite representable relation algebras. Then there exists a polynomial-time reduction from NSP(A) to NSP(A × B). This lemma has a converse; we are not aware of any reference for this lemma, but it will be highly useful in our classification project. Lemma 3.2. Let A1 and A2 be finite representable relation al… view at source ↗
Figures from the paper (24 more)
Figure 4
Figure 4. Figure 4: The number of (simple, integral) relation algebras with 0–4 atoms and 1–16 elements. [PITH_FULL_IMAGE:figures/full_fig_p023_4.png]
Figure 5
Figure 5. Figure 5: Integral relation algebras with at most four atoms and at least one flexible atom. [PITH_FULL_IMAGE:figures/full_fig_p025_5.png]
Figure 6
Figure 6. Figure 6: A 2-point-amalgamation diagram of size 5. [PITH_FULL_IMAGE:figures/full_fig_p026_6.png]
Figure 7
Figure 7. Figure 7: Integral relation algebras with at most four atoms which do not have a normal representa [PITH_FULL_IMAGE:figures/full_fig_p026_7.png]
Figure 8
Figure 8. Figure 8: Not-so-small relation algebras formed by 2-cycle products of small relation algebras. [PITH_FULL_IMAGE:figures/full_fig_p028_8.png]
Figure 9
Figure 9. Figure 9: Failure of AP(3, 2, 4) for 3965 [PITH_FULL_IMAGE:figures/full_fig_p031_9.png]
Figure 10
Figure 10. Figure 10: Failure of AP(3, 2, 6) for 6265. Edges colored blue, red, and black are labeled a, b, and c, respectively. Lemma 4.12. Let A ∈ RRA be a finite relation algebra with an equivalence relation e ∈ A. Furthermore, let S be the set of atoms a ∈ A0 such that a ̸≤ e ◦ e. If S…
Figure 11
Figure 11. Figure 11: AP(3, 2, 4) fails for 5665. Proposition 4.27. 5665 does not have a fully universal representation. Proof. Consider the diagram from [PITH_FULL_IMAGE:figures/full_fig_p039_11.png]
Figure 12
Figure 12. Figure 12: Relation algebras where Theorem 5.8 applies. hence m(b, a, b) = b. Putting it all together, we apply m to the allowed triples (Id, b, b),(Id, a, a),(b, b, a) and get (m(Id,Id, b), m(b, a, b), m(b, a, a)) = (Id, b, a) ∈ CyA0 , which is a contradiction. Finally, assume …
Figure 13
Figure 13. Figure 13: In every solution g to this 1937-network, we have g(x1, x2) = g(y1, y2). is well-defined. Note that, since the behaviour of f on {x, y} is conservative, ξ(Pol(B)) is a clone on the two-element set {x, y}. It is easy to see that ξ is a clone homomorphism. Note that if …
Figure 14
Figure 14. Figure 14: Detail from the normal representation B of 2765. Here, (x, y) ∈ ER and (x ′ , y′ ) ̸∈ ER. x1 z1 y1 x2 z2 y2 a∪Id a∪Id a∪Id a∪Id c∪Id c∪Id c∪Id b∪Id b∪Id [PITH_FULL_IMAGE:figures/full_fig_p045_14.png]
Figure 15
Figure 15. Figure 15: In every solution g to this 2765-network, we have g(x1, x2) = g(y1, y2). The consistent reduced atomic 2765-networks are exactly those in which c only appears in rainbow triangles, i.e., in triples (x, y, z) such that {x, y, z} = {a, b, c}. Let R = (R; ER) be the Rado…
Figure 16
Figure 16. Figure 16: In every solution g to this 2965-network, we have g(x1, x2) = g(y1, y2). is a {c,Id}-minority m: Since (m(b, c, b), m(Id, c,Id), m(b,Id, b)) has to be an allowed triple, m(Id, c,Id) = c and m(b,Id, b) ∈ {b,Id}, it follows that m(b, c, b) = c. Analogously, since (m(c, …
Figure 17
Figure 17. Figure 17: In this 3337-network, a directed edge stands for r, and an undirected edge stands for (r ∪ r˘). In every solution g to it, we have g(x0, x1) = g(y0, y1). Proof. We present a primitive positive interpretation in B of the structure ({0, 1}; NAE). It then follows from Pr…
Figure 18
Figure 18. Figure 18: An edge stands for (r∪r˘). In every solution g to this 3537-network, we have g(x0, x1) = g(y0, y1). p1 p2 p3 p4 q1 q2 q3 r∪Id r∪Id r∪Id r∪r˘ r r∪r˘ r r∪r˘ r r [PITH_FULL_IMAGE:figures/full_fig_p048_18.png]
Figure 19
Figure 19. Figure 19: In every solution g to this 3537-network, at least one of g(p1, q1), g(p2, q2) and g(p3, q3) is equal to r. Proof. We present a primitive positive interpretation in B of the structure ({0, 1}; R, S), where R := {0, 1} 3 \ {(0, 0, 0)} and S := {(0, 1),(1, 0)}. It is ea…
Figure 20
Figure 20. Figure 20: An edge stands for (r ∪r˘). In every solution g to this 3537-network, we have g(q0, q1) ̸= g(p0, p1). 48 [PITH_FULL_IMAGE:figures/full_fig_p048_20.png]
Figure 21
Figure 21. Figure 21: The 3037-network E(x0, x1, y0, y1) encodes equal orientation of two (r ∪ r˘)-edges: In every solution g to it, we have g(x0, x1) = g(y0, y1). p1 p2 p3 p4 q1 q2 q3 a∪Id a∪Id a∪Id r∪r˘ r r∪r˘ r r∪r˘ r a [PITH_FULL_IMAGE:figures/full_fig_p050_21.png]
Figure 22
Figure 22. Figure 22: The 3037-network S(p1, p2, p3, p4, q1, q2, q3): In every solution g to it, at least one of g(p1, q1), g(p2, q2), and g(p3, q3) is equal to r. p0 q0 p1 q1 r r∪r˘ a∪r r∪r˘ a [PITH_FULL_IMAGE:figures/full_fig_p050_22.png]
Figure 23
Figure 23. Figure 23: The 3037-network T(p0, p1, q0, q1): In every solution g to it, we have that g(p0, p1) = r implies g(q0, q1) = ˘r. 50 [PITH_FULL_IMAGE:figures/full_fig_p050_23.png]
Figure 24
Figure 24. Figure 24: The 3165-network E(x0, x1, y0, y1): In every solution g to it, we have g(x0, x1) = g(y0, y1). p1 p2 p3 p4 q1 q2 q3 c∪Id c∪Id c∪Id b∪c b∪c b∪c b∪c b∪c b∪c c [PITH_FULL_IMAGE:figures/full_fig_p051_24.png]
Figure 25
Figure 25. Figure 25: The 3165-network S(p1, p2, p3, p4, q1, q2, q3): In every solution g to this 3165-network, at least one of g(p1, q1), g(p2, q2) and g(p3, q3) is equal to c. The network (V ′ , f) is defined as follows: For every variable x ∈ V , we add two fresh variables x0 and x1 to …
Figure 26
Figure 26. Figure 26: The 3165-network T(p1, p2, p3): In every solution g to it, we have that g(p1, p2) = b or g(p2, p3) = b. 51 [PITH_FULL_IMAGE:figures/full_fig_p051_26.png]
Figure 27
Figure 27. Figure 27: Binary symmetric polymorphisms of the atom structures for the relation algebras [PITH_FULL_IMAGE:figures/full_fig_p053_27.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

64 extracted references · 59 canonical work pages

  1. [1]

    Hajnal Andr \' e ka and Roger D. Maddux. Representations for small relation algebras. Notre Dame Journal of Formal Logic , 35(4):550--562, 1994

    work page 1994

  2. [2]

    Datalog and constraint satisfaction with infinite templates

    Manuel Bodirsky and V\'ictor Dalmau. Datalog and constraint satisfaction with infinite templates. Journal on Computer and System Sciences , 79:79--100, 2013. A preliminary version appeared in the proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS'05)

    work page 2013

  3. [3]

    Hereditary First-Order Logic: the tractable quantifier prefix classes

    Manuel Bodirsky and Santiago Guzmán-Pro. Hereditary first-order model checking, 2024. Preprint available under https://arxiv.org/abs/2411.10860

    work page Pith review arXiv 2024

  4. [4]

    The G eneric C ircular T riangle- F ree G raph

    Manuel Bodirsky and Santiago Guzmán-Pro. The G eneric C ircular T riangle- F ree G raph. Journal of G raph T heory , 109(4):426--445, 2025

    work page 2025

  5. [5]

    Point algebras for temporal reasoning: Algorithms and complexity

    Mathias Broxvall and Peter Jonsson. Point algebras for temporal reasoning: Algorithms and complexity. Artificial Intelligence , 149(2):179--220, 2003

    work page 2003

  6. [6]

    Quasi-transitive digraphs

    J rgen Bang-Jensen and Jing Huang. Quasi-transitive digraphs. Journal of Graph Theory , 20(2):141--161, 1995

    1995

  7. [7]

    Pure dominance constraints

    Manuel Bodirsky and Martin Kutz. Pure dominance constraints. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS) , pages 287--298, 2002

    work page 2002

  8. [8]

    Determining the consistency of partial tree descriptions

    Manuel Bodirsky and Martin Kutz. Determining the consistency of partial tree descriptions. Artificial Intelligence , 171:185--196, 2007

    work page 2007

Show all 64 references
  1. [9]

    The complexity of temporal constraint satisfaction problems

    Manuel Bodirsky and Jan K\'ara. The complexity of temporal constraint satisfaction problems. Journal of the ACM , 57(2):1--41, 2009. An extended abstract appeared in the Proceedings of the Symposium on Theory of Computing (STOC)

    2009

  2. [10]

    Hardness of network satisfaction for relation algebras with normal representations

    Manuel Bodirsky and Simon Kn\" a uer. Hardness of network satisfaction for relation algebras with normal representations. In Relational and Algebraic Methods in Computer Science , pages 31--46. Springer International Publishing, 2020

    2020

  3. [11]

    The complexity of network satisfaction problems for symmetric relation algebras with a flexible atom

    Manuel Bodirsky and Simon Kn \" a uer. The complexity of network satisfaction problems for symmetric relation algebras with a flexible atom. J. Artif. Intell. Res. , 75:1701--1744, 2022

    2022

  4. [12]

    The complexity of network satisfaction problems for symmetric relation algebras with a flexible atom

    Manuel Bodirsky and Simon Kn \" a uer. The complexity of network satisfaction problems for symmetric relation algebras with a flexible atom. Journal of Artificial Intelligence Research , 75, 2022

    2022

  5. [13]

    Network satisfaction problems solved by k -consistency

    Manuel Bodirsky and Simon Kn \" a uer. Network satisfaction problems solved by k -consistency. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany , pages 116:1--116:20, 2023

    2023

  6. [14]

    The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems

    Libor Barto, Michael Kompatscher, Miroslav Ol s \' a k, Trung Van Pham, and Michael Pinsker. The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems. In Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science -- ...

    2017 arXiv

  7. [15]

    Krokhin, and Jakub Opr s al

    Jakub Bul \' n, Andrei A. Krokhin, and Jakub Opr s al. Algebraic approach to promise constraint satisfaction. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019 , pages 602--613, 2019

    2019

  8. [16]

    Constraint satisfaction problems for reducts of homogeneous graphs

    Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and Andr \' a s Pongr \' a cz. Constraint satisfaction problems for reducts of homogeneous graphs. SIAM Journal on Computing , 48(4):1224--1264, 2019. A conference version appeared in the Proceedings of the 43rd International C...

    2019

  9. [17]

    Finite relation algebras with normal representations

    Manuel Bodirsky. Finite relation algebras with normal representations. In Relational and Algebraic Methods in Computer Science - 17th International Conference, RAMiCS 2018, Groningen, The Netherlands, October 29 - November 1, 2018, Proceedings , pages 3--17, 2018

    2018

  10. [18]

    Complexity of Infinite-Domain Constraint Satisfaction

    Manuel Bodirsky. Complexity of Infinite-Domain Constraint Satisfaction . Lecture Notes in Logic (52). Cambridge University Press, Cambridge, United Kingdom; New York, NY, 2021

    2021

  11. [19]

    The wonderland of reflections

    Libor Barto, Jakub Opr s al, and Michael Pinsker. The wonderland of reflections. Israel Journal of Mathematics , 223(1):363--398, 2018

    2018

  12. [20]

    Reducts of R amsey structures

    Manuel Bodirsky and Michael Pinsker. Reducts of R amsey structures. AMS Contemporary Mathematics (Model Theoretic Methods in Finite Combinatorics) , 558:489--519, 2011

    2011

  13. [21]

    Topological birkhoff

    Manuel Bodirsky and Michael Pinsker. Topological birkhoff. Transactions of the American Mathematical Society , 367, 03 2012

    2012

  14. [22]

    Schaefer's theorem for graphs

    Manuel Bodirsky and Michael Pinsker. Schaefer's theorem for graphs. Journal of the ACM , 62(3):52 pages (article number 19), 2015. A conference version appeared in the Proceedings of STOC 2011, pages 655-664

    2015

  15. [23]

    The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems

    Libor Barto and Michael Pinsker. The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. In Proceedings of the 31th A nnual IEEE S ymposium on L ogic in C omputer S cience -- LICS '16 , pages 615--622, 2016. Preprint arXiv:1602.04353

    2016 arXiv

  16. [24]

    Projective clone homomorphisms

    Manuel Bodirsky, Michael Pinsker, and Andr\' a s Pongr\'acz. Projective clone homomorphisms. Journal of Symbolic Logic , 86(1):148--161, 2021

    2021

  17. [25]

    Burris and Hanamantagouda P

    Stanley N. Burris and Hanamantagouda P. Sankappanavar. A Course in Universal Algebra . Springer Verlag, Berlin, 1981

    1981

  18. [26]

    Andrei A. Bulatov. Tractable conservative constraint satisfaction problems. In Proceedings of the Symposium on Logic in Computer Science (LICS) , pages 321--330, Ottawa, Canada, 2003

    2003

  19. [27]

    Andrei A. Bulatov. A dichotomy theorem for nonuniform CSP s. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, B erkeley, CA , USA , O ctober 15-17 , pages 319--330, 2017

    2017

  20. [28]

    Peter J. Cameron. The random graph. R. L. Graham and J. Ne s et r il, Editors, The Mathematics of Paul Erd\" o s , 1996

    1996

  21. [29]

    The complexity of the constraint satisfaction problem for small relation algebras

    Matteo Cristiani and Robin Hirsch. The complexity of the constraint satisfaction problem for small relation algebras. Artificial Intelligence Journal , 156:177--196, 2004

    2004

  22. [30]

    Homogeneous digraphs I

    Gregory Cherlin. Homogeneous digraphs I . T he imprimitive case. Logic Colloquium 1985 , 1987

    1985

  23. [31]

    Gregory L. Cherlin. The classification of countable homogeneous directed graphs and countable homogeneous n -tournaments. AMS Memoir , 131(621), January 1998

    1998

  24. [32]

    Homogeneous ordered graphs and metrically homogeneous graphs, 2020

    Gregory Cherlin. Homogeneous ordered graphs and metrically homogeneous graphs, 2020. Preprint

    2020

  25. [33]

    Constructions of color schemes

    Stephen Comer. Constructions of color schemes. Acta Universitatis Carolinae. Mathematica et Physica , 24, 01 1983

    1983

  26. [34]

    Stephen D. Comer. Extension of polygroups by polygroups and their representations using color schemes. In Ralph S. Freese and Octavio C. Garcia, editors, Universal Algebra and Lattice Theory , pages 91--103, Berlin, Heidelberg, 1983. Springer Berlin Heidelberg

    1983

  27. [35]

    Stephen D. Comer. A remark on chromatic polygroups. Congressus Numerantium , 38:85--95, 1983

    1983

  28. [36]

    Stephen D. Comer. Combinatorial aspects of relations. Algebra Universalis , 18(1):77--94, February 1984

    1984

  29. [37]

    On datalog vs

    Anuj Dawar and Stephan Kreutzer. On datalog vs. LFP . In Luca Aceto, Ivan Damg rd, Leslie Ann Goldberg, Magn \' u s M. Halld \' o rsson, Anna Ing \' o lfsd \' o ttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008,...

    2008

  30. [38]

    Relation algebras and their application in temporal and spatial reasoning

    Ivo D \" u ntsch. Relation algebras and their application in temporal and spatial reasoning. Artificial Intelligence Review , 23:315--357, 2005

    2005

  31. [39]

    R. E. Greenwood and A. M. Gleason. Combinatorial relations and chromatic graphs. Canadian Journal of Mathematics , 7:1–7, 1955

    1955

  32. [40]

    A guide to NP -completeness

    Michael Garey and David Johnson. A guide to NP -completeness . CSLI Press, Stanford, 1978

    1978

  33. [41]

    Ward Henson

    C. Ward Henson. Countable homogeneous relational systems and categorical theories. Journal of Symbolic Logic , 37:494--500, 1972

    1972

  34. [42]

    Hirsch and I

    R. Hirsch and I. Hodkinson. Representability is not decidable for finite relation algebras. Transactions of the American Mathematical Society , 353(4):1387--1401), 2001

    2001

  35. [43]

    Relation Algebras by Games

    Robin Hirsch and Ian Hodkinson. Relation Algebras by Games . North Holland, 2002

    2002

  36. [44]

    Relation algebras of intervals

    Robin Hirsch. Relation algebras of intervals. Artificial Intelligence Journal , 83:1--29, 1996

    1996

  37. [45]

    A finite relation algebra with undecidable network satisfaction problem

    Robin Hirsch. A finite relation algebra with undecidable network satisfaction problem. Logic Journal of the IGPL , 7(4):547--554, 1999

    1999

  38. [46]

    Twenty years of N e s et r il's classification programme of R amsey classes

    Jan Hubi c ka and Mat e j Kone c n \`y . Twenty years of N e s et r il's classification programme of R amsey classes. Preprint arXiv:2501.17293, 2025

    2025

  39. [47]

    A shorter model theory

    Wilfrid Hodges. A shorter model theory . Cambridge University Press, Cambridge, 1997

    1997

  40. [48]

    Boolean algebras with operators

    Bjarni Jónnson and Alfred Tarski. Boolean algebras with operators. American Journal of Mathematics , 74(1):127--162, 1952

    1952

  41. [49]

    Constraint satisfaction over the random tournament, 2018

    Simon Kn \"a uer. Constraint satisfaction over the random tournament, 2018. Master Thesis at the Institute of Algebra, TU Dresden

    2018

  42. [50]

    Richard E. Ladner. On the structure of polynomial time reducibility. Journal of the ACM , 22(1):155--171, 1975

    1975

  43. [51]

    Lachlan and Robert E

    Alistair H. Lachlan and Robert E. Woodrow. Countable ultrahomogeneous undirected graphs. Transactions of the AMS , 262(1):51--94, 1980

    1980

  44. [52]

    R. Lyndon. The representation of relational algebras. Annals of Mathematics , 51(3):707--729, 1950

    1950

  45. [53]

    A survey of homogeneous structures

    Dugald Macpherson. A survey of homogeneous structures. Discrete Mathematics , 311(15):1599--1634, 2011

    2011

  46. [54]

    Roger D. Maddux. Finite symmetric integral relation algebras with no 3-cycles. In Renate A. Schmidt, editor, Relations and Kleene Algebra in Computer Science, 9th International Conference on Relational Methods in Computer Science and 4th International Workshop on Applications ...

    2006

  47. [55]

    Relation Algebras: Volume 150

    Roger Duncan Maddux. Relation Algebras: Volume 150 . Studies in logic and the foundations of mathematics. Elsevier Science, London, England, May 2006

    2006

  48. [56]

    On representable relation algebras

    Donald Monk. On representable relation algebras. Michigan Mathematical Journal , 11(3):207 -- 210, 1964

    1964

  49. [57]

    The Two-Valued Iterative Systems of Mathematical Logic

    Emil Leon Post. The Two-Valued Iterative Systems of Mathematical Logic . H. Milford, Oxford university press, London,, 1941

    1941

  50. [58]

    Schaefer

    Thomas J. Schaefer. The complexity of satisfiability problems. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC 1978, San Diego, California, USA , pages 216--226, 1978

    1978

  51. [59]

    Contributions to the theory of models

    Alfred Tarski. Contributions to the theory of models. Koninklijke Nederlandse Akademie van Wetenschappen, Proceedings , 58:56–64, 1955

    1955

  52. [60]

    Constraint propagation algorithms for temporal reasoning: A revised report

    Marc Vilain, Henry Kautz, and Peter van Beek. Constraint propagation algorithms for temporal reasoning: A revised report. Reading in Qualitative Reasoning about Physical Systems , pages 373--381, 1989

    1989

  53. [61]

    Tarjan, and Eugene L

    Jacobo Valdes, Robert E. Tarjan, and Eugene L. Lawler. The recognition of series parallel digraphs. SIAM Journal on Computing , 11(2):298--313, 1982

    1982

  54. [62]

    Dmitriy N. Zhuk. A proof of CSP dichotomy conjecture. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, B erkeley, CA , USA , O ctober 15-17 , pages 331--342, 2017. https://arxiv.org/abs/1704.01914

    2017 arXiv

  55. [63]

    A proof of the CSP dichotomy conjecture

    Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM , 67(5):30:1--30:78, 2020

    2020

  56. [64]

    Hypergroups

    Paul-Hermann Zieschang. Hypergroups . Springer, 2023

    2023

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.