Subpower membership conjecture for algebras with few subpowers

Let A\mathbb{A} be a finite algebra, and say that it has few subpowers when the equivalent conditions in the source's Few Subpowers theorem hold. Given a finite subset SAnS\subseteq \mathbb{A}^n and an element xAnx\in \mathbb{A}^n, the subpower membership problem asks whether xx belongs to the subalgebra of An\mathbb{A}^n generated by SS. Few-subpowers subpower-membership conjecture. If A\mathbb{A} has few subpowers, then the subpower membership problem can be solved in polynomial time. The source presents this as an open question; general instances can be EXPTIME-complete, while stronger hardness results cover many algebras without few subpowers.

Sources & referencesView supporting material

Primary source

Zarathustra Brady, “Notes on CSPs and Polymorphisms”, arXiv:2210.07383 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.