# How does complexity of a counting problem influence wether it admits a closed form formula or not?

In https://arxiv.org/abs/1412.1505, the section "Results on Data Complexity" mentions the fact that since the authors are about to proove $$\#P_1$$ complexity for weighted model counting in Fist Order Logic. Hence, such a problem cannot admit a closed form formula.

Why is this claim true ? Are there counting problems which are hard in general but admit a closed form counting formula ?

PS:

1. FO$$^2$$ admits model counting in polynomial time with respect to the domain elements, and also admits a closed form formula for counting.
• I do not know of any #P-complete problem that has a closed form formula. If any one of them did, then probably all of them would, using the poly-time reductions between the problems (most of which are in fact projections, so would map a closed-form formula to another closed-form formula). In general I think the notion of "closed form formula" is a bit...loose? But for most things that people would say are "closed form formulas", they are easy to compute. Oct 23, 2020 at 16:44
• Not an answer but perhaps of interest: the existence and complexity of evaluation of closed-form formulas are studied in enumerative combinatorics, see, e.g., Sec. 1.2 in arxiv.org/abs/1803.06636 for some definitions of formula complexity. Unlike in propositional logic though, here one has just one instance per problem size. Jan 13, 2021 at 19:42