2016/09/13 by Payne, Ian
#FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.1609.03943
To any fixed, finite relational structure, \mathbbD, there is an associated decision problem, CSP(\mathbbD), which is a restricted version of the constraint satisfaction problem. In [8], the so called "algebraic approach" to the constraint satisfaction problem was established. The authors showed that to any finite relational structure, there is a corresponding finite algebra, and that the complexity of CSP(\mathbbD) depends only on this algebra. Therefore, they associate a decision problem, CSP(\bf D) to an algebra, \bf D, and ignore the relational structure. Their "algebraic dichotomy conjecture" suggests that a technical condition on \bf D implies CSP(\bf D) has a polynomial time algorithm. A significant sub-problem is the case when some reduct of \bf D has a congruence, θ so that \bf D/θ has operations implying the local consistency algorithm correctly solves CSP(\bf D/θ), and each θ-equivalence class, B, has operations implying the few subpowers algorithm correctly solves CSP(\bf B). We give an algorithm for the case when \bf D has a binary term operation which is a 2-semilattice operation on some quotient, \bf D/θ of \bf D, a projection on each θ-class, and two other technical conditions are satisfied. Using this, we confirm the conjecture in the case that \bf D is in the join of two varieties, one of which has an edge term and the other is term equivalent to the variety of 2-semilattices.