Geodesic
Deciding the Existence of Minority Terms
Canadian mathematical bulletin, Tome 63 (2020) no. 3, pp. 577-591

Voir la notice de l'article provenant de la source Cambridge

DOI

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.
DOI : 10.4153/S0008439519000651
Mots-clés : Maltsev condition, minority term, computational complexity 
Kazda, Alexandr; Opršal, Jakub; Valeriote, Matt; Zhuk, Dmitriy. Deciding the Existence of Minority Terms. Canadian mathematical bulletin, Tome 63 (2020) no. 3, pp. 577-591. doi: 10.4153/S0008439519000651
@article{10_4153_S0008439519000651,
     author = {Kazda, Alexandr and Opr\v{s}al, Jakub and Valeriote, Matt and Zhuk, Dmitriy},
     title = {Deciding the {Existence} of {Minority} {Terms}},
     journal = {Canadian mathematical bulletin},
     pages = {577--591},
     year = {2020},
     volume = {63},
     number = {3},
     doi = {10.4153/S0008439519000651},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/S0008439519000651/}
}
TY  - JOUR
AU  - Kazda, Alexandr
AU  - Opršal, Jakub
AU  - Valeriote, Matt
AU  - Zhuk, Dmitriy
TI  - Deciding the Existence of Minority Terms
JO  - Canadian mathematical bulletin
PY  - 2020
SP  - 577
EP  - 591
VL  - 63
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4153/S0008439519000651/
DO  - 10.4153/S0008439519000651
ID  - 10_4153_S0008439519000651
ER  - 
%0 Journal Article
%A Kazda, Alexandr
%A Opršal, Jakub
%A Valeriote, Matt
%A Zhuk, Dmitriy
%T Deciding the Existence of Minority Terms
%J Canadian mathematical bulletin
%D 2020
%P 577-591
%V 63
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4153/S0008439519000651/
%R 10.4153/S0008439519000651
%F 10_4153_S0008439519000651

Cité par Sources :