Marcel Jackson

The Finite Basis Problem is hard

Since as far back as Bernhard Neumann's work in the 1930s, the question of when and whether a finite algebra has a finite basis for its equational theory has been one of the central narratives of universal algebra. The specific question of decidability of this property was popularised by Alfred Tarski in the 1950s and eventually solved in the negative by Ralph McKenzie in the 1990s. Despite McKenzie's ground-breaking effort, there remains no clear evidence that the finite based problem is computationally challenging in any "naturally occurring" class of algebras. We show that the finite basis problem is NP-hard in the class of semilattice-ordered semigroups (also known as additively-idempotent semirings).