INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS Academic Article uri icon

abstract

  • 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.

publication date

  • February 2006