Testing for a Semilattice Term

This paper investigates the computational complexity of deciding if a given finite algebra is an expansion of a semilattice. In general this problem is known to be EXP-TIME complete, and we show that even for idempotent algebras, this problem remains hard. This result is in contrast to a series of results that show that similar decision problems turn out to be tractable.