#### 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.

#### Recommended Citation

Shriner, Jeffrey Alan, "Hardness Results for the Subpower Membership Problem" (2018). *Mathematics Graduate Theses & Dissertations*. 63.

https://scholar.colorado.edu/math_gradetds/63