ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let A\mathbb{A} be a reduct of a finitely bounded homogeneous structure. Let S\mathbb{S} be the finite structure defined by

S:=({0,1};{(0,0,1),(0,1,0),(1,0,0)}).\mathbb{S}:=(\{0,1\};\{(0,0,1),(0,1,0),(1,0,0)\}).

A structure is homomorphically equivalent to another when homomorphisms exist in both directions, and a primitive-positive interpretation is an interpretation defined by primitive-positive formulas.

Homomorphic-equivalence CSP dichotomy conjecture. One of the following holds:

  1. S\mathbb{S} is homomorphically equivalent to a structure with a pp-interpretation in A\mathbb{A}, and consequently CSP⁡(A)\operatorname{CSP}(\mathbb{A}) is NP-complete.
  2. CSP⁡(A)\operatorname{CSP}(\mathbb{A}) is polynomial-time solvable.

This is the younger dichotomy conjecture described in the source. It seeks to avoid passing first to a model-complete core; the paper proves that the two conjectures are equivalent, while the general dichotomy remains unresolved.

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.