Deciding the Existence of Minority Terms

Kazda, Alexandr; Opršal, Jakub; Valeriote, Matt; Zhuk, Dmitriy

doi:10.4153/s0008439519000651

Deciding the Existence of Minority Terms

Kazda, Alexandr; Opršal, Jakub; Valeriote, Matt; Zhuk, Dmitriy

Authors

Alexandr Kazda

Jakub Opršal

Matt Valeriote

Dmitriy Zhuk

Abstract

This paper investigates the computational complexity of deciding if a given finite idempotent algebra has a ternary term operation m that satisfies the minority equations m(y,x,x)≈m(x,y,x)≈m(x,x,y)≈y . We show that a common polynomial-time approach to testing for this type of condition will not work in this case and that this decision problem lies in the class NP.

Citation

Kazda, A., Opršal, J., Valeriote, M., & Zhuk, D. (2020). Deciding the Existence of Minority Terms. Canadian Mathematical Bulletin, 63(3), 577-591. https://doi.org/10.4153/s0008439519000651

Journal Article Type	Article
Online Publication Date	Oct 24, 2019
Publication Date	2020-09
Deposit Date	Sep 14, 2020
Publicly Available Date	Oct 7, 2020
Journal	Canadian Mathematical Bulletin
Print ISSN	0008-4395
Electronic ISSN	1496-4287
Publisher	Cambridge University Press
Peer Reviewed	Peer Reviewed
Volume	63
Issue	3
Pages	577-591
DOI	https://doi.org/10.4153/s0008439519000651
Related Public URLs	https://arxiv.org/abs/1901.00316

Files

Accepted Journal Article (218 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/

Copyright Statement
This article has been published in a revised form in Canadian mathematical bulletin http://doi.org/10.4153/S0008439519000651. This version is published under a Creative Commons CC-BY-NC-ND. No commercial re-distribution or re-use allowed. Derivative works cannot be distributed. © Canadian Mathematical Society 2019.