1 results
Deciding the Existence of Minority Terms
- Part of
-
- Journal:
- Canadian Mathematical Bulletin / Volume 63 / Issue 3 / September 2020
- Published online by Cambridge University Press:
- 24 October 2019, pp. 577-591
- Print publication:
- September 2020
-
- Article
- Export citation
-
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 .
