FINDING TYPE SETS IS NP-HARD
David Hobby · International Journal of Algebra and Computation · 1991
It is shown that determining the type set of the variety generated by a finite algebra is a P-Space-hard problem. This is done by interpreting into it the P-Space-complete problem of determining if a given function is a composition of a set of unary functions on a set. Specifically, the given function is a composition of the others just when the type 3 is not in the type set of the variety generated by the algebra that is constructed. A lemma that restricts the types that are possible in the variety generated by a given algebra is also given.