Restricted CSP tractability conjecture for reducts of finitely bounded homogeneous structures
Restricted CSP tractability conjecture for reducts of finitely bounded homogeneous structures
Let be a reduct of a finitely bounded homogeneous structure, and let be a finite structure. The restricted constraint satisfaction problem has as its infinite template and as its finite restriction. Let be the complete graph on three vertices, let be the finite structure used in the restricted pp-construction, and let rpp-construct mean restricted primitive-positive construct.
Restricted CSP tractability conjecture. If the restricted -template does not rpp-construct , then is polynomial-time solvable.
The paper states that this conjecture is equivalent to the tractability conjecture above for restricted CSP templates with finite restrictions, and presents the general tractability conjecture as wide open.
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
Santiago Guzmán-Pro and Barnaby Martin, “Restricted CSPs and F-free Digraph Algorithmics”, arXiv:2502.17596 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.