Nonlinear idempotent Mal'tsev Condition Satisfaction Problems: why semilattices are hard and lattices are easier

Abstract: 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.

computational complexitycategory theorylogic

Audience: researchers in the topic

PALS Panglobal Algebra and Logic Seminar

Series comments: The PALS seminar is a research and learning seminar organized by the algebra and logic research group of the Department of Mathematics at the University of Colorado at Boulder. The scope of the seminar includes all topics with links to algebra, logic, or their applications, like general algebra, logic, model theory, category theory, set theory, set-theoretic topology, or theoretical computer science. Please contact one of the organizers for the Zoom password, to join the mailing list or if you want to speak.