Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/25721
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Valeriote, Matthew | - |
dc.contributor.author | Rooney, J P | - |
dc.date.accessioned | 2020-08-24T17:54:21Z | - |
dc.date.available | 2020-08-24T17:54:21Z | - |
dc.date.issued | 2020 | - |
dc.identifier.uri | http://hdl.handle.net/11375/25721 | - |
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. | en_US |
dc.language.iso | en | en_US |
dc.subject | Universal Algebra | en_US |
dc.subject | General Algebra | en_US |
dc.subject | Mal'tsev Conditions | en_US |
dc.subject | Mal'tsev Condition Satisfaction Problems | en_US |
dc.subject | MCSP | en_US |
dc.subject | Complexity | en_US |
dc.subject | Algebra | en_US |
dc.subject | Constraint Satisfaction | en_US |
dc.subject | CSP | en_US |
dc.title | On the Complexity of Several Mal'tsev Condition Satisfaction Problems | en_US |
dc.title.alternative | Mal'tsev Condition Satisfaction Problems | en_US |
dc.type | Thesis | en_US |
dc.contributor.department | Mathematics and Statistics | en_US |
dc.description.degreetype | Thesis | en_US |
dc.description.degree | Doctor of Philosophy (PhD) | en_US |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Rooney_J_P_202007_PhD.pdf | 963.24 kB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.