An algebraic hardness criterion for surjective constraint satisfaction

作者：Chen Hubie^*

来源：ALGEBRA UNIVERSALIS, 2014, 72(4): 393-401.

DOI：10.1007/s00012-014-0308-x

• surjective constraint satisfaction
• clones

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 a 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. We present an algebraic condition on the polymorphism clone of B and prove that it is sufficient for the hardness of the surjective CSP on a finite structure B, in the sense that this problem admits a reduction from a certain fixed-structure CSP. To our knowledge, this is the first result that allows one to use algebraic information from a relational structure B to infer information on the complexity hardness of surjective constraint satisfaction on B. A corollary of our result is that on any finite non-trivial structure having only essentially unary polymorphisms, surjective constraint satisfaction is NP-complete.

• 出版日期2014-12