Deciding the Existence of Minority Terms
Alexandr Kazda, Jakub Opršal, MATTHEW A. VALERIOTE, Dmitriy N. Zhuk · Canadian Mathematical Bulletin · 2019
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.