Back to search

McMaster University

On the Complexity of Several Mal'tsev Condition Satisfaction Problems

Abstract

dc:description.abstract

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.

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 × 9

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*

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

Rooney, J P. On the Complexity of Several Mal'tsev Condition Satisfaction Problems. 2020. http://hdl.handle.net/11375/25721