INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
Marcel Jackson, Ralph McKenzie · International Journal of Algebra and Computation · 2006
We show that a number of natural membership problems for classes associated with finite semigroups are computationally difficult. In particular, we construct a 55-element semigroup S such that the finite membership problem for the variety of semigroups generated by S interprets the graph 3-colorability problem.