Results on the Computational Complexity of Linear Idempotent Mal'cev Conditions

Abstract

<p>In this thesis we examine the computational complexity of determining the satisfaction of various Mal'cev conditions. First we present a novel classification of linear idempotent Mal'cev conditions based on the form of the equations with which they are represented. Using this classification we present a class of conditions which can be detected in polynomial time when examining idempotent algebras. Next we generalize an existing result of Freese and Valeriote by presenting another class of conditions whose satisfaction is exponential time hard to detect in the general case, and en route we prove that it is equally hard to detect local constant terms. The final new contribution is an extension of a recent result of Maróti to a subclass class of weak Mal'cev conditions, proving that their detection is decidable and providing a rough upperbound for the complexity of the provided algorithm for said detection. We close the thesis by reviewing the current state of knowledge with respect to determining satisfaction of linear idempotent Mal'cev conditions.</p>