Skip to main content

Research Repository

Advanced Search

Deciding the Existence of Minority Terms

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

Deciding the Existence of Minority Terms Thumbnail


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





You might also like



Downloadable Citations