Hardness Results for the Subpower Membership Problem

Graduate Thesis Or Dissertation

Public Deposited

Citations

Citeable URL: https://scholar.colorado.edu/concern/graduate_thesis_or_dissertations/3f462547h

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.

Creator