Commutative idempotent groupoids and the constraint satisfaction problem

A restatement of the Algebraic Dichotomy Conjecture, due to Maroti and McKenzie, postulates that if a finite algebra A possesses a weak near-unanimity term, then the corresponding constraint satisfaction problem is tractable. A binary operation is weak near-unanimity if and only if it is both commutative and idempotent. Thus if the dichotomy conjecture is true, any finite commutative, idempotent groupoid (CI groupoid) will be tractable. It is known that every semilattice (i.e., an associative CI groupoid) is tractable. A groupoid identity is of Bol–Moufang type if the same three variables appear on either side, one of the variables is repeated, the remaining two variables appear once, and the variables appear in the same order on either side (for example, $${x(x(yz)) \approx (x(xy))z}$$x(x(yz))≈(x(xy))z). These identities can be thought of as generalizations of associativity. We show that there are exactly 8 varieties of CI groupoids defined by a single additional identity of Bol–Moufang type, derive some of their important structural properties, and use that structure theory to show that 7 of the varieties are tractable. We also characterize the finite members of the variety of CI groupoids satisfying the self-distributive law $${x(yz) \approx (xy)(xz)}$$x(yz)≈(xy)(xz), and show that they are tractable.

Related papers:

title: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
abstract: This paper starts with the project of finding a large subclass of NP which exhibits a dichotomy. The approach is to find this subclass via syntactic prescriptions. While the paper does not achieve this goal, it does isolate a class (of problems specified by) "monotone monadic SNP without inequality" which may exhibit this dichotomy. We justify the placing of all these restrictions by showing, essentially using Ladner's theorem, that classes obtained by using only two of the above three restrictions do not show this dichotomy. We then explore the structure of this class. We show that all problems in this class reduce to the seemingly simpler class CSP. We divide CSP into subclasses and try to unify the collection of all known polytime algorithms for CSP problems and extract properties that make CSP problems NP-hard. This is where the second part of the title, "a study through Datalog and group theory," comes in. We present conjectures about this class which would end in showing the dichotomy.

title: Closure properties of constraints
abstract: Many combinatorial search problems can be expressed as “constraint satisfaction problems” and this class of problems is known to be NP-complete in general. In this paper, we investigate the subclasses that arise from restricting the possible constraint types. We first show that any set of constraints that does not give rise to an NP-complete class of problems must satisfy a certain type of algebraic closure condition. We then investigate all the different possible forms of this algebraic closure property, and establish which of these are sufficient to ensure tractability. As examples, we show that all known classes of tractable constraints over finite domains can be characterized by such an algebraic closure property. Finally, we describe a simple computational procedure that can be used to determine the closure properties of a given set of constraints. This procedure involves solving a particular constraint satisfaction problem, which we call an “indicator problem.”

title: Classifying the Complexity of Constraints Using Finite Algebras
abstract: Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. Here we show that any set of relations used to specify the allowed forms of constraints can be associated with a finite universal algebra and we explore how the computational complexity of the corresponding constraint satisfaction problem is connected to the properties of this algebra. Hence, we completely translate the problem of classifying the complexity of restricted constraint satisfaction problems into the language of universal algebra. 
We introduce a notion of "tractable algebra," and investigate how the tractability of an algebra relates to the tractability of the smaller algebras which may be derived from it, including its subalgebras and homomorphic images. This allows us to reduce significantly the types of algebras which need to be classified. Using our results we also show that if the decision problem associated with a given collection of constraint types can be solved efficiently, then so can the corresponding search problem. We then classify all finite strictly simple surjective algebras with respect to tractability, obtaining a dichotomy theorem which generalizes Schaefer's dichotomy for the generalized satisfiability problem. Finally, we suggest a possible general algebraic criterion for distinguishing the tractable and intractable cases of the constraint satisfaction problem.

title: Recent Results on the Algebraic Approach to the CSP
abstract: We describe an algebraic approach to the constraint satisfaction problem (CSP) and present recent results on the CSP that make use of, in an essential way, this algebraic framework.

title: Combinatorial problems raised from 2-semilattices
abstract: provides a general framework for many combinatorial problems. In [A.A. Bulatov, A.A. Krokhin, P.G. Jeavons, Classifying the complexity of constraints using finite algebras,  (3) (2005) 720–742; P.G. Jeavons, On the algebraic structure of combinatorial problems,  (1998) 185–204] and then in [A.A. Bulatov, P.G. Jeavons, Algebraic structures in combinatorial problems, Technical Report MATH-AL-4-2001, Technische Universitat Dresden, Dresden, Germany, 2001], a new approach to the study of the CSP has been developed which uses properties of universal algebras assigned to certain subclasses of the CSP such that the time complexity and other properties of subclasses can be derived from the properties of the assigned algebras. In this paper we briefly survey this approach, and then prove that problem classes corresponding to finite 2-semilattices, that is groupoids satisfying the identities x x = x , x y = y x , x ( x y ) = ( x x ) y , can be solved in polynomial time. Making use of this result we classify finite conservative groupoids, and 4-element algebras with minimal clone of term operations with respect to the complexity of the corresponding CSP-class.

title: On the Algebraic Structure of Combinatorial Problems
abstract: We describe a general algebraic formulation for a wide range of combinatorial problems including Satisfiability, Graph Colorability and Graph Isomorphism In this formulation each problem instance is represented by a pair of relational structures, and the solutions to a given instance are homomorphisms between these relational structures. The corresponding decision problem consists of deciding whether or not any such homomorphisms exist. We then demonstrate that the complexity of solving this decision problem is determined in many cases by simple algebraic properties of the relational structures involved. This result is used to identify tractable subproblems of Satisfiability , and to provide a simple test to establish whether a given set of Boolean relations gives rise to one of these tractable subproblems.

title: Tractability and Learnability Arising from Algebras with Few Subpowers
abstract: A constraint language $\Gamma$ on a finite set $A$ has been called polynomially expressive if the number of $n$-ary relations expressible by $\exists\wedge$-atomic formulas over $\Gamma$ is bounded by $\exp(O(n^k))$ for some constant $k$. It has recently been discovered that this property is characterized by the existence of a $(k+1)$-ary polymorphism satisfying certain identities; such polymorphisms are called $k$-edge operations and include Mal'cev and near-unanimity operations as special cases. We prove that if $\Gamma$ is any constraint language which, for some $k>1$, has a $k$-edge operation as a polymorphism, then the constraint satisfaction problem for $\langle\Gamma\rangle$ (the closure of $\Gamma$ under $\exists\wedge$-atomic expressibility) is globally tractable. We also show that the set of relations definable over $\Gamma$ using quantified generalized formulas is polynomially exactly learnable using improper equivalence queries.

title: A Simple Algorithm for Mal'tsev Constraints
abstract: A Mal'tsev operation is a ternary operation $\varphi$ that satisfies the identities $\varphi(x,y,y) = \varphi(y,y,x) = x$. Constraint satisfaction problems involving constraints invariant under a Mal'tsev operation constitute an important class of constraint satisfaction problems, which includes the affine satisfiability problem, subgroup and near subgroup constraints, and many others. It is also known that any tractable case of the counting constraint satisfaction problem involves only Mal'tsev constraints. 
 
The first algorithm solving the arbitrary constraint satisfaction problem with Mal'tsev constraints has been given by Bulatov. However, this algorithm is very sophisticated and relies heavily on advanced algebraic machinery. In this paper, we give a different and much simpler algorithm for this type of constraint.

title: Generalized majority-minority operations are tractable
abstract: Let A be a finite set and let /spl phi/ : A/sup k//spl rarr/A with k/spl ges/3 be a k-ary operation on A. We say that /spl phi/ is a generalized majority-minority (GMM) operation if for all a, b /spl isin/ A we have that /spl phi/(x, y,...,y) = /spl phi/(y, x,..,y) =...=/spl phi/(y, y,..,x) = y for all x, y /spl isin/ {a, b} or /spl phi/{x, y,..,y) = /spl phi/(y, y,..,x) = x for all x, y /spl isin/ {a, b}. Near-unanimity and Mal'tsev operations are particular instances of GMM operations. We prove that every CSP instance where all constraint relations are invariant under a (fixed) GMM operation is solvable in polynomial time. This constitutes one of the largest tractable cases of the CSP.

title: Quasigroups, Loops, and Associative Laws
abstract: We investigate the question of which weakenings of the associative law imply that a quasigroup is a loop. In particular, we completely settle the question for all laws of “Bol–Moufang type” (those written with four variables, three of which are distinct).

title: The varieties of loops of Bol-Moufang type
abstract: A loop identity is of Bol-Moufang type if two of its three variables occur once on each side, the third variable occurs twice on each side, and the order in which the variables appear on both sides is the same, viz. ((xy)x)z = x(y(xz)). Loop varieties defined by one identity of Bol-Moufang type include groups, Bol loops, Moufang loops and C-loops. We show that there are exactly 14 such varieties, and determine all inclusions between them, providing all necessary counterexamples, too. This extends and completes the programme of Fenyves [Fe69].

title: The varieties of quasigroups of Bol–Moufang type: An equational reasoning approach
abstract: A quasigroup identity is of Bol–Moufang type if two of its three variables occur once on each side, the third variable occurs twice on each side, the order in which the variables appear on both sides is the same, and the only binary operation used is the multiplication, viz. ( ( x y ) x ) z = x ( y ( x z ) ) . Many well-known varieties of quasigroups are of Bol–Moufang type. We show that there are exactly 26 such varieties, determine all inclusions between them, and provide all necessary counterexamples. We also determine which of these varieties consist of loops or one-sided loops, and fully describe the varieties of commutative quasigroups of Bol–Moufang type. Some of the proofs are computer-generated.

title: Varieties of Steiner loops and Steiner quasigroups
abstract: 1. I n t r o d u c t i o n . A Steiner Triple System (STS) is a pair ( P , B) where P is a set of points and B is a set of 3-elenient subsets of P called blocks (or triples) such tha t for distinct p, q £ P there is a unique block b Ç B with {p, q) C b. There are two well-known methods for turning Steiner Triple Systems into algebras; both methods are due to R. H. Bruck . Each method gives rise to a var ie ty of algebras; in this paper we will s tudy these varieties. The first method turns the STS (P , B) into a Steiner quasigroup (squag) based on P : define x = x and otherwise xy = z where {x, y, z} £ B. Note tha t ( P ; •) satisfies: i) x = x, ii) xy = yx, iii) x(xy) = y. Conversely, any algebra ( P ; •) satifying i) — iii) generates a STS (P, B) where B is the set of 3-element subalgebras of ( P ; •). Thus the class of all squags forms a var ie ty which is denoted by Sq. The second method turns the STS (P , B) into a Steiner loop (sloop) based o n P U {1} (where 1 $ P ) : define Ix = x l = x, x = 1 and otherwise x;y = s where {x, y, z) £ P . Note tha t (P U {1} ; •) satisfies a) Ix = x, b) x = 1, c) X3> = yx, d) x(x;y) = 3/. Conversely, any algebra ( P ' ; • , 1) satisfying a) — d) generates a 5 T S ( P ' — { l j , B) where B is the set of all 3-element subsets of P — {1} which together with 1 form a subalgebra. Thus the class of all sloops forms a variety which is denoted by SI. We assume tha t the reader is familiar with the basic concepts of universal algebra; for details and notational conventions, see .