Answers are grounded in this paper and cite their sources.
The subpower membership problem for a finite family K of finite algebras asks whether a target tuple belongs to the subalgebra generated by given tuples in a product of members of K. We prove that this problem is decidable in deterministic polynomial time for every fixed finite family of finite algebras of a common finite signature with a common cube term; in particular, for every fixed finite algebra of finite signature with few subpowers. Bulatov, Mayr and Szendrei proved this for families in residually small varieties, proved membership in NP in general, and recorded the general question, which goes back to Idziak, Marković, McKenzie, Valeriote and Willard. The proof follows the architecture of an earlier manuscript of the author on Mal'tsev algebras and combines it with the reduction of Mayr and Szendrei to subdirectly irreducible algebras with central monoliths. The changes are local. From an edge term E we use the term m(x,y,z) = E(y,x,z,...,z). It satisfies m(x,x,z) = z identically, but m(x,y,y) = x only inside the classes of a central congruence. An elementary argument from the term condition nevertheless gives central coordinates whose coefficients do not depend on the quotient. A minimal-image normalization, which is never computed, produces an image carrying a multiplication with a one-sided identity and bijective left translations; bounded-support linear equations separate relations closed under such multiplications. Exact saturation of bounded-support indicator features then decides membership relative to the quotient, and an induction through strictly smaller sections of the original algebras completes the argument. All running-time exponents in this proof depend on the fixed family. We also consider the version in which the algebras are part of the input and are given by full operation tables. When the dimension d of the cube term is not bounded, there is no algorithm with running time f(d)·N^O(1) unless FPT = W[2], and none with running time n^o(d)·N^O(1) unless FPT = W[1], where N is the input length and n is the number of coordinates. This holds already for two-element algebras whose only basic operation is a near-unanimity operation, and for these algebras time N^O(d) suffices. We explain where the proof for fixed families depends on the family. Algorithms that are uniform in the algebras, for each fixed dimension, are the subject of a companion paper.
No takes yet. Share an insight, caveat, or question.
Asterios Gkantzounis (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: