The tractability conjecture for CSPs of reducts of finitely bounded homogeneous structures
Let be a normal representation of a finite relation algebra . A primitive-positive interpretation is an interpretation defined by primitive-positive formulas, and pp-constructs a structure if it pp-interprets a homomorphically equivalent structure. Let denote the Boolean structure with the not-all-equal relation. Write for the constraint satisfaction problem of and for the network satisfaction problem of .
Tractability conjecture. If does not pp-construct , then
If the stated pp-construction condition holds, the CSP is known to be -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.
References
- 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).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.