The tractability conjecture for CSPs of reducts of finitely bounded homogeneous structures

From papers

Let B\mathfrak{B} be a normal representation of a finite relation algebra A\mathbf{A}. A primitive-positive interpretation is an interpretation defined by primitive-positive formulas, and B\mathfrak{B} pp-constructs a structure if it pp-interprets a homomorphically equivalent structure. Let ({0,1};NAE)(\{0,1\};\operatorname{NAE}) denote the Boolean structure with the not-all-equal relation. Write CSP(B)\operatorname{CSP}(\mathfrak{B}) for the constraint satisfaction problem of B\mathfrak{B} and NSP(A)\operatorname{NSP}(\mathbf{A}) for the network satisfaction problem of A\mathbf{A}.

Tractability conjecture. If B\mathfrak{B} does not pp-construct ({0,1};NAE)(\{0,1\};\operatorname{NAE}), then

CSP(B) and NSP(A) are in P.\operatorname{CSP}(\mathfrak{B})\text{ and }\operatorname{NSP}(\mathbf{A})\text{ are in }\operatorname{\mathbf{P}}.

If the stated pp-construction condition holds, the CSP is known to be NP\operatorname{\mathbf{NP}}-hard; the conjecture asserts polynomial-time tractability in the complementary case. It is presented as a specialization of the broader dichotomy conjecture for reducts of finitely bounded homogeneous structures.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Manuel Bodirsky, Moritz Jahn, Simon Knäuer, Matěj Konečný and Paul Winkler, “The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms”, arXiv:2507.09324 (2026).

Solutions 0

No solutions have been posted yet.