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 University Press

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

[1] Bergman, C., Universal algebra: Fundamentals and selected topics. Pure and Applied Mathematics (Boca Raton), 301, CRC Press, Boca Raton, FL, 2012. Google Scholar

[2] Bulatov, A., Mayr, P., and Szendrei, Á., The subpower membership problem for finite algebras with cube terms. Log. Methods Comput. Sci. 15(2019), no. 1, Paper No. 11. Google Scholar

[3] Burris, S. and Sankappanavar, H. P., A course in universal algebra. Graduate Texts in Mathematics, 78, Springer-Verlag, New York-Berlin, 1981. Google Scholar | DOI

[4] Dalmau, V., Generalized majority-minority operations are tractable. Log. Methods in Comput. Sci. 2(2006), no. 4, 4:1. https://doi.org/10.2168/LMCS-2(4:1)2006. Google Scholar | DOI

[5] Freese, R. and Valeriote, M. A., On the complexity of some Maltsev conditions. Internat. J. Algebra Comput. 19(2009), 41–77. https://doi.org/10.1142/S0218196709004956 Google Scholar | DOI

[6] García, O. C. and Taylor, W., The lattice of interpretability types of varieties. Mem. Amer. Math. Soc. 50(1984), no. 305. https://doi.org/10.1090/memo/0305. Google Scholar

[7] Horowitz, J., Computational complexity of various Mal’cev conditions. Internat. J. Algebra Comput. 23(2013), 1521–1531. https://doi.org/10.1142/S0218196713500343 Google Scholar | DOI

[8] Kazda, A. and Valeriote, M., Deciding some Maltsev conditions in finite idempotent algebras. J. Symbolic Logic., to appear. Google Scholar

[9] Kearnes, K. A. and Kiss, E. W., The shape of congruence lattices. Mem. Amer. Math. Soc. 222(2013), no. 1046. https://doi.org/10.1090/S0065-9266-2012-00667-8 Google Scholar

[10] Kozik, M., A finite set of functions with an EXPTIME-complete composition problem. Theoret. Comput. Sci. 407(2008), 330–341. https://doi.org/10.1016/j.tcs.2008.06.057 Google Scholar | DOI

[11] Mayr, P., The subpower membership problem for Mal’cev algebras. Internat. J. Algebra Comput. 22(2012), 1250075. https://doi.org/10.1142/S0218196712500750 Google Scholar | DOI

[12] Olšák, M., The weakest nontrivial idempotent equations. Bull. London Math. Soc. 49(2017), 1028–1047. https://doi.org/10.1112/blms.12097 Google Scholar | DOI

[13] Valeriote, M. and Willard, R., Idempotent n-permutable varieties. Bull. Lond. Math. Soc. 46(2014), 870–880. https://doi.org/10.1112/blms/bdu044 Google Scholar | DOI

Cité par Sources :