Complexity of the finite algebra membership problem for varieties

An algebra is a nonempty set equipped with a system of finitary operations. The equational theory of a class K of algebras is the set of all equations true in each algebra belonging to K . A class of algebras is a variety if it can be axiomatized by some set of equations. The variety generated by an algebra A is just the variety axiomatized by the equational theory of A. Equational theories that can be axiomatized by some finite set of equations are finitely based.;The focus of this dissertation is the finite algebra membership problem of varieties: for any variety V generated by a finite algebra A to decide whether a given finite algebra B∈ V. To make the problem nontrivial A must not be finitely based.;We attach two complexity measures to a finite algebra. The first is the computational complexity of the membership problem of the variety it generates. We construct a 7-element algebra with two binary operations which generates a variety whose finite algebra membership problem is NP-complete.;The second complexity measure is defined by the equational bound : a function b (n) is called an equational bound of an algebra A if the membership of any algebra B in the variety generated by A can be decided by testing those equations true in A of length at most b (n), where n is the number of elements in B. We construct a number of small algebras each generating a variety whose finite algebra membership problem has equational complexity bounded by a linear function but not bounded by any function (like nloglogn or n1-3 with 0 < 3 < 1) which is sublinear.;This line of research is related to recent algebraic investigations by J. Ježek, R. McKenzie, G. McNulty, R. Willard, and others.