McMaster University
On the Complexity of Several Mal'tsev Condition Satisfaction Problems
Abstract
dc:description.abstractIn this thesis we derive novel results on the complexity of idempotent Mal'tsev condition satisfaction problems. For a Mal'tsev condition M, the idempotent M- satisfaction problem is the decision problem defined via: INPUT: A finite idempotent algebra A. QUESTION: Does A satisfy M? In particular we are able to prove that this decision problem is in the complexity class NP whenever M satisfi es one of the following conditions: 1. M is a strong Mal'tsev condition which implies the existence of a near unanimity term. 2. M is a strong Mal'tsev condition of height < 1 (see Definition 5.1.1). As a porism of these two results, we are able to derive the stronger result that the complexity of the idempotent M-satisfaction problem is in NP whenever M is a strong Mal'tsev condition which implies the existence of an edge term. On top of this we also outline a polynomial-time algorithm for the idempotent M-satisfaction problem when M is a linear strong Mal'tsev condition which implies the existence of a near unanimity term. We also examine the related search problem in which the goal is to produce operation tables of term operations of the algebra A which witness that A satisfies the Mal'tsev condition M whenever such terms exist (and otherwise correctly decide that such terms do not exist). We outline polynomial-time algorithms for this search problem for various strong Mal'tsev conditions. We close the thesis with a short list of open problems as suggested directions for further research.
Degree
thesis:*- Department dc:contributor.department
- Mathematics and Statistics
- Year dc:date.issued
- 2020
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Rooney, J P
- Advisor dc:contributor.advisor
-
- Valeriote, Matthew
Subjects
dc:subject × 9Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Identifier URI
- https://doi.org/10.71548/11613