Chen's few-subpowers expressive-rate conjecture
Let be a constraint language, and let be the logarithm of the number of distinct -variable relations definable by primitive positive formulas over . Chen's expressive-rate conjecture. The function always either grows as a polynomial or as an exponential function. In the polynomial-growth case, the class of definable relations is efficiently learnable and the associated CSP can be solved in polynomial time. The surrounding text says that this conjecture was resolved through the theory of algebras with few subpowers.
References
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
No solutions have been posted yet.