No Access

THE SUBPOWER MEMBERSHIP PROBLEM FOR MAL'CEV ALGEBRAS

PETER MAYR

CAUL, Centro de Álgebra da Universidade de Lisboa, Av. Prof. Gama Pinto 2, 1649-003 Lisboa, Portugal

Current address: Institute for Algebra, JKU Linz, Altenberger Straße 69, 4040 Linz, Austria.

https://doi.org/10.1142/S0218196712500750Cited by:10 (Source: Crossref)

Abstract

Given tuples a₁, …, a_k and b in Aⁿ for some algebraic structure A, the subpower membership problem asks whether b is in the subalgebra of Aⁿ that is generated by a₁, …, a_k. For A a finite group, there is a folklore algorithm which decides this problem in time polynomial in n and k. We show that the subpower membership problem for any finite Mal'cev algebra is in NP and give a polynomial time algorithm for any finite Mal'cev algebra with finite signature and prime power size that has a nilpotent reduct. In particular, this yields a polynomial algorithm for finite rings, vector spaces, algebras over fields, Lie rings and for nilpotent loops of prime power order.

Keywords:

AMSC: 08A40 (20B40)

References

E. Aichinger, Proc. Amer. Math. Soc. 138(10), 3501 (2010), DOI: 10.1090/S0002-9939-2010-10395-7. Crossref, Web of Science, Google Scholar
K. A. Baker and A. F. Pixley, Math. Z. 143(2), 165 (1975), DOI: 10.1007/BF01187059. Crossref, Web of Science, Google Scholar
A. Bulatov and V. Dalmau, SIAM J. Comput. 36(1), 16 (2006), DOI: 10.1137/050628957. Crossref, Web of Science, Google Scholar
C. W. Curtis and I. Reiner , Methods of Representation Theory , With Applications to Finite Groups and Orders I ( John Wiley & Sons , New York , 1981 ) . Google Scholar
D. Daly and P. Vojtěchovský, J. Algebra 322(11), 4080 (2009), DOI: 10.1016/j.jalgebra.2009.03.042. Crossref, Web of Science, Google Scholar
R. Freese and R. McKenzie , Commutator Theory for Congruence Modular Varieties, London Mathematical Society Lecture Note Series 125 ( Cambridge University Press , 1987 ) . Google Scholar
M. Furst, J. Hopcroft and E. Luks, Polynomial-time algorithms for permutation groups, 21st Annual Symp. Foundations of Computer Science, Syracuse (IEEE, New York, 1980) pp. 36–41. Google Scholar
D. Hobby and R. McKenzie , The Structure of Finite Algebras , Contemporary Mathematics 76 ( American Mathematical Society , 1988 ) . Crossref, Google Scholar
M. Kozik, Theoret. Comput. Sci. 407(3), 330 (2008), DOI: 10.1016/j.tcs.2008.06.057. Crossref, Web of Science, Google Scholar
P. Mayr, Algebra Universalis 65, 193 (2011), DOI: 10.1007/s00012-011-0124-5. Crossref, Web of Science, Google Scholar
R. N. McKenzie , G. F. McNulty and W. F. Taylor , Algebras, Lattices, Varieties I ( Wadsworth & Brooks/Cole Advanced Books & Software , Monterey, California , 1987 ) . Google Scholar
E. L. Post , The Two-Valued Iterative Systems of Mathematical Logic , Annals of Mathematics Studies 5 ( Princeton University Press , Princeton, NJ , 1941 ) . Google Scholar
R. Willard , Four unsolved problems in congruence permutable varieties , Talk at International Conference on Order, Algebra, and Logics ( Vanderbilt University , Nashville , 2007 ) . Google Scholar