ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let \bA\bA be an algebra with a Taylor term in its clone, and let RR be a finite set of relations compatible with \bA\bA. Write CSP(R)CSP(R) for the constraint satisfaction problem over RR. An algebra is idempotent if every basic operation satisfies f(a,,,a)=af(a,,,a)=a whenever all its arguments are equal. Algebraic CSP dichotomy conjecture. If \bA\bA has a Taylor term in its clone, then CSP(R)CSP(R) is tractable. Conversely, if \bA\bA is idempotent and has no Taylor term in its clone, then there exists a finite set RR of relations such that CSP(R)CSP(R) is NP\text{NP}-complete. This is the universal-algebraic reformulation of the Feder–Vardi dichotomy, linking tractability to Taylor terms. The source states that the second sentence had already been established; the full dichotomy is now solved.

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.