ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let B{\mathfrak B} be a reduct of a finitely bounded countable homogeneous structure. A primitive positive interpretation of a graph in B{\mathfrak B} is an interpretation using primitive positive formulas, and a graph is homomorphically equivalent to K3K_3 when it admits homomorphisms to and from the triangle K3K_3.

Feder–Vardi tractability conjecture. If B{\mathfrak B} does not interpret primitively positively a graph which is homomorphically equivalent to K3K_3, then

CSP⁡(B)\operatorname{CSP}({\mathfrak B})

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.