Tue, 1 March 2022, 1 pm MST
In their 2020 article "Deciding some Mal'tsev conditions in finite idempotent algebras" Kazda and Valeriote conjecture that for a linear strong Mal'tsev condition the associated idempotent Mal'tsev condition satisfaction problem (MCSP) will always be polynomial-time decidable. In an earlier-published 2019 article Freese, Nation and Valeriote showed that testing for a semilattice term (a nonlinear condition) is EXPTIME-complete even for idempotent algebras.
While preparing my PhD thesis I investigated the hypothesis that nonlinear Mal'tsev conditions might always be EXPTIME-complete to detect. I was able to prove that there are nonlinear Mal'tsev conditions whose related idempotent MCSPs are in the class NP. Assuming that NP is not EXPTIME this provides the first examples of nonlinear Mal'tsev conditions whose idempotent MCSPs are not EXPTIME-complete. The existence of lattice terms is one such example.
In this talk we briefly revisit the 2019 result of Freese, Nation and Valeriote before sketching the details of my proof that detection of lattice terms in an idempotent algebra is an NP problem.