The tractability conjecture for CSPs of reducts of finitely bounded homogeneous structures
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.
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
Sign in to submit a solution.
No solutions have been posted yet.