Chen's complexity conjecture for the surjective constraint satisfaction problem
Statement
Let be a finite domain and let be a constraint language on . Write for the ordinary constraint satisfaction problem and for the problem asking whether an instance has a surjective satisfying assignment. Let denote the unary singleton relations. Chen's conjecture. For any constraint language , the problems
are polynomially equivalent. This conjecture was proposed as a polymorphism-based characterization of SCSP complexity, but the paper disproves it by giving a counterexample; it is known for two-element domains.
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.