Deciding the existence of minority terms

Autor:	Kazda, Alexandr, Opršal, Jakub, Valeriote, Matt, Zhuk, Dmitriy
Rok vydání:	2019
Předmět:	Mathematics - Logic Computer Science - Computational Complexity Mathematics - Rings and Algebras 68Q25 (Primary) 03B05 08A40 (Secondary)
Druh dokumentu:	Working Paper
Popis:	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.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1901.00316 Zobrazit plný text záznamu View this record from Arxiv