Algebraic CSP dichotomy conjecture
Statement
Let be an algebra with a Taylor term in its clone, and let be a finite set of relations compatible with . Write for the constraint satisfaction problem over . An algebra is idempotent if every basic operation satisfies whenever all its arguments are equal. Algebraic CSP dichotomy conjecture. If has a Taylor term in its clone, then is tractable. Conversely, if is idempotent and has no Taylor term in its clone, then there exists a finite set of relations such that is -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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.