Back to search

McMaster University

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

Abstract

dc:description.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>

Degree

thesis:*
Department dc:contributor.department
Mathematics and Statistics
Year dc:date.issued
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Horowitz, Jonah
Advisor dc:contributor.advisor
  • Valeriote, Matt

Subjects

dc:subject × 3

Identifiers

dc:identifier.*
Dc Identifier Other
opendissertations/6562
7565
2372077

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Horowitz, Jonah. Results on the Computational Complexity of Linear Idempotent Mal'cev Conditions. 2012. http://hdl.handle.net/11375/11606