Polynomial-Time Subpower Membership for Finite Algebras with Cube Terms: Fixed Families and Limits of Uniformity

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.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-14
DOI
https://doi.org/10.5281/zenodo.24222967
Citations
1
Primary Topic
Advanced Algebra and Logic
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Polynomial-Time Subpower Membership for Finite Algebras with Cube Terms: Fixed Families and Limits of Uniformity

Asterios Gkantzounis
1 citations
Zenodo (CERN European Organization for Nuclear Research)
Advanced Algebra and Logic
preprint

Polynomial-Time Subpower Membership for Finite Algebras with Cube Terms: Fixed Families and Limits of Uniformity

Asterios Gkantzounis
preprint en
1 citations

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Technical University of Crete (GR)
Advanced Algebra and Logic
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon