Testing for a semilattice term (Q1732802)

A \textit{semilattice term} in an algebra \(A\) means a binary term which is commutative, associative and idempotent. A binary term \(b(x,y)\) is called a \textit{flat semilattice term} if \(A\) has an absorbing element \(0\) such that \(b(a,a)=a\) for every element a and \(b(a,b)=0\) for different elements \(a, b\). The authors prove two remarkable results concerning the computational complexity as follows: Theorem 3.4. The problem of deciding, given a finite idempotent algebra \(A\), whether or not it has a flat semilattice term, is in P. Theorem 4.1 The problem of deciding, given an idempotent algebra \(A\) and its element 1, whether or not it has a semilattice term \(b(x,y)\) such that \(b(a,1)=a=b(1,a)\) for all elements \(a\) in \(A\) is EXP-TIME complete.