Return to search

On the Complexity of Several Mal'tsev Condition Satisfaction Problems / Mal'tsev Condition Satisfaction Problems

In 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. / Thesis / Doctor of Philosophy (PhD)

Identiferoai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/25721
Date January 2020
CreatorsRooney, J P
ContributorsValeriote, Matthew, Mathematics and Statistics
Source SetsMcMaster University
LanguageEnglish
Detected LanguageEnglish
TypeThesis

Page generated in 0.0063 seconds