Chen's few-subpowers expressive-rate conjecture

About 4 years old · traced to

Let Γ\Gamma be a constraint language, and let r(n)r(n) be the logarithm of the number of distinct nn-variable relations definable by primitive positive formulas over Γ\Gamma. Chen's expressive-rate conjecture. The function r(n)r(n) 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

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.