The tractability conjecture for CSPs of reducts of finitely bounded homogeneous structures
Statement
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.
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.