Date of Award

Spring 1-1-2018

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

First Advisor

Agnes Szendrei

Second Advisor

William DeMeo

Third Advisor

Peter Mayr

Fourth Advisor

Keith Kearnes

Abstract

We first provide an example of a finite algebra with a Taylor term whose subpower membership problem is NP-hard. We then prove that for any consistent strong linear Maltsev condition M which does not imply the existence of a cube term, there exists a finite algebra satisfying M whose subpower membership problem is EXPTIME-complete. We characterize consistent strong linear Maltsev conditions which do not imply the existence of a cube term, and show as a corollary that there are finite algebras which generate congruence distributive and congruence k-permutable (k ≥ 3) varieties whose subpower membership problem is EXPTIME-complete. Finally, we show that the spectrum of complexities of the problems SMP(𝔸) for finite algebras 𝔸 in varieties which are congruence distributive and congruence k-permutable (k ≥ 3) is fuller than P and EXPTIME-complete by giving examples of finite algebras in such a variety whose subpower membership problems are NP-complete and PSPACE-complete, respectively.

Share

COinS