Restricted CSP tractability conjecture for reducts of finitely bounded homogeneous structures
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.