Feder–Vardi tractability conjecture for infinite-domain CSPs
Statement
Let be a reduct of a finitely bounded countable homogeneous structure. A primitive positive interpretation of a graph in is an interpretation using primitive positive formulas, and a graph is homomorphically equivalent to when it admits homomorphisms to and from the triangle .
Feder–Vardi tractability conjecture. If does not interpret primitively positively a graph which is homomorphically equivalent to , then
is in P.
The conjecture is an infinite-domain analogue of the finite-domain CSP dichotomy and gives a structural condition for tractability. The paper states that the corresponding P versus NP-complete dichotomy is known for MMSNP, but the tractability conjecture in the present infinite-domain setting is presented here without a resolution.
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.