Date of Award
Doctor of Philosophy (PhD)
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.
Shriner, Jeffrey Alan, "Hardness Results for the Subpower Membership Problem" (2018). Mathematics Graduate Theses & Dissertations. 63.