Subpower membership conjecture for algebras with few subpowers
Subpower membership conjecture for algebras with few subpowers
Let 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 and an element , the subpower membership problem asks whether belongs to the subalgebra of generated by . Few-subpowers subpower-membership conjecture. If 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.