Restricted CSP tractability conjecture for reducts of finitely bounded homogeneous structures

From papers

Let A{\mathbb A} be a reduct of a finitely bounded homogeneous structure, and let B{\mathbb B} be a finite structure. The restricted constraint satisfaction problem RCSP(A,B)\operatorname{RCSP}({\mathbb A},{\mathbb B}) has A{\mathbb A} as its infinite template and B{\mathbb B} as its finite restriction. Let K3{\mathbb K}_3 be the complete graph on three vertices, let L{\mathbb L} 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 CSP\operatorname{CSP}-template does not rpp-construct (K3,L)({\mathbb K}_3,{\mathbb L}), then RCSP(A,B)\operatorname{RCSP}({\mathbb A},{\mathbb B}) 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

No solutions have been posted yet.