An algebraic hardness criterion for surjective constraint satisfaction. (Q485113)

The constraint satisfaction problem (CSP) on a relational structure \(B\) is to decide, given a set of constraints on variables where the relations come from \(B\), whether or not there is an assignment to the variables satisfying all of the constraints. The surjective CSP is the variant where one decides the existence of a surjective satisfying assignment onto the universe of \(B\). Equivalently, given a structure \(A\) over the signature of \(B\), one can decide whether or not there is a surjective homomorphism from \(A\) to \(B\). Main result: Suppose \(B\) is a finite structure which is not a singleton. If each polymorphism of \(B\) is essentially unary then the surjective CSP on \(B\) is NP-complete.