On some complexity problems in finite algebras
Marcin Kozik, Ralph McKenzie · 2004
This work contains constructions of finite algebras which are “complex” according to three different complexity measures. These constructions are modifications of the construction of Ralph McKenzie's A(T). They produce finite algebras that “model” computations of Turing machines on various inputs. In this way, we obtain a finite algebra generating a variety with PSPACE-complete membership problem and another algebra with exponentially growing γ A function. The final construction produces a finite algebra that is able to model a computation of a Turing machine on an exponentially long tape. This gives an example of a finite algebra with EXPSPACE-hard membership problem and a doubly exponentially growing βA function. Examples of finite algebra of such complexity classes were not known before.