Dichotomies for classes of homomorphism problems involving unary functions

Feder, T.; Madelaine, F.R.; Stewart, I.A.

Abstract

We study non-uniform constraint satisfaction problems where the underlying signature contains constant and function symbols as well as relation symbols. Amongst our results are the following. We establish a dichotomy result for the class of non-uniform constraint satisfaction problems over the signature consisting of one unary function symbol by showing that every such problem is either complete for L, via very restricted logical reductions, or trivial (depending upon whether the template function has a fixed point or not). We show that the class of non-uniform constraint satisfaction problems whose templates are structures over the signature $\lambda_2$ consisting of two unary function symbols reflects the full computational significance of the class of non-uniform constraint satisfaction problems over relational structures. We prove a dichotomy result for the class of non-uniform constraint satisfaction problems where the template is a $\lambda_2$-structure with the property that the two unary functions involved are the reverse of one another, in that every such problem is either solvable in polynomial-time or NP-complete. Finally, we extend some of our results to the situation where instances of non-uniform constraint satisfaction problems come equipped with lists of elements of the template structure which restrict the set of allowable homomorphisms.

Citation

Feder, T., Madelaine, F., & Stewart, I. (2004). Dichotomies for classes of homomorphism problems involving unary functions. Theoretical Computer Science, 314(1-2), 1-43. https://doi.org/10.1016/j.tcs.2003.12.015

• Journal Article Type: Article
• Publication Date: 2004-02
• Deposit Date: Oct 10, 2008
• Publicly Available Date: Oct 10, 2008
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 314
• Issue: 1-2
• Pages: 1-43
• DOI: https://doi.org/10.1016/j.tcs.2003.12.015
• Keywords: Computational complexity, Constraint satisfaction, Dichotomies.
• Public URL: https://durham-repository.worktribe.com/output/1627850
• Related Public URLs: http://www.dur.ac.uk/i.a.stewart/Papers/dichotomies.pdf