Home
Scholarly Works
Deciding the existence of minority terms
Preprint

Deciding the existence of minority terms

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) \approx m(x,y,x) \approx m(x,x,y) \approx 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.

Authors

Kazda A; Opršal J; Valeriote M; Zhuk D

Publication date

January 2, 2019

DOI

10.48550/arxiv.1901.00316

Preprint server

arXiv
View published work (Non-McMaster Users)

Contact the Experts team