Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/11606
Title: | Results on the Computational Complexity of Linear Idempotent Mal'cev Conditions |
Authors: | Horowitz, Jonah |
Advisor: | Valeriote, Matt |
Department: | Mathematics and Statistics |
Keywords: | universal algebra;csp;Algebra;Algebra |
Publication Date: | Apr-2012 |
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> |
URI: | http://hdl.handle.net/11375/11606 |
Identifier: | opendissertations/6562 7565 2372077 |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
fulltext.pdf | 583.07 kB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.