#### Campus Units

Mathematics

#### Document Type

Article

#### Publication Version

Accepted Manuscript

#### Publication Date

6-2015

#### Journal or Book Title

Algebra Universalis

#### Volume

73

#### Issue

3-4

#### First Page

391

#### Last Page

417

#### DOI

10.1007/s00012-015-0323-6

#### Abstract

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))≈(x(xy))z" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">x(x(yz))≈(x(xy))zx(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)≈(xy)(xz)" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">x(yz)≈(xy)(xz)x(yz)≈(xy)(xz), and show that they are tractable.

#### Copyright Owner

Springer Basel

#### Copyright Date

2015

#### Language

en

#### File Format

application/pdf

#### Recommended Citation

Bergman, Clifford and Failing, David, "Commutative idempotent groupoids and the constraint satisfaction problem" (2015). *Mathematics Publications*. 157.

https://lib.dr.iastate.edu/math_pubs/157

## Comments

The final publication is available at Springer via https://doi.org/10.1007/s00012-015-0323-6. Bergman, Clifford, and David Failing. "Commutative idempotent groupoids and the constraint satisfaction problem."

Algebra Universalis73, no. 3-4 (2015): 391-417. Posted with permission.