Uniform Subpower Membership for Finite Mal'tsev Algebras

The subpower membership problem asks whether a given tuple lies in the subalgebra of a finite power generated by given tuples. We give a deterministic polynomial-time algorithm for a uniform version of this problem for Mal'tsev algebras, in which the algebras are part of the input and are given by full operation tables. The coordinate algebras may differ, and they share a designated basic Mal'tsev operation. From the generators the algorithm prepares a predicate for membership in every projection onto selected coordinates, and the polynomial bounds have an absolute exponent, made explicit in the paper. As a corollary, subpower membership is in polynomial time for every fixed finite Mal'tsev algebra, without a nilpotence assumption. Moreover, the same conclusion holds for powers of a single algebra that is only promised to have a Mal'tsev term in its original signature, when no term, table or circuit for it is supplied; given the first result, this is polynomially equivalent to computing, under the promise, the table of a Mal'tsev operation in the original term clone. The algorithm combines an enumeration of meet-irreducible congruences in modular lattices, a coarsening of the subdirectly irreducible decomposition of Bulatov, Mayr and Szendrei that avoids testing similarity, affine charts on centralizer blocks, a central closure engine working with permutation groups of polynomial degree, and a universal function-valued extension whose zero section recovers the generated relation. A size-stratified flat query procedure prevents recursive growth.