Combinatorial problems raised from 2-semilattices (Q2496183)

The Constraint Satisfaction Problem (CSP) provides a framework for many combinatorial problems. On the basis of a description of certain subclasses of CSP by means of certain properties of universal algebras, time complexity characterizations and other properties can be derived. In the paper the author proves that problem classes corresponding to finite 2-semilattices, which are groupoids satisfying the identities \(xx=x\), \(xy= yx\), \(x(xy)=(xx)y\), can be solved in polynomial time. Due to this result, finite conservative groupoids and 4-element algebras with minimal clone of term operations are classified with respect to the complexity of the corresponding CSP-class.