<p>In <a href="https://arxiv.org/abs/1412.1505" rel="nofollow noreferrer">https://arxiv.org/abs/1412.1505</a>, the section &quot;Results on Data Complexity&quot; mentions the fact that since the authors are about to proove <span class="math-container">$\#P_1$</span> complexity for weighted model counting in Fist Order Logic. Hence, such a problem cannot admit a closed form formula.</p>
<p>Why is this claim true ? Are there counting problems which are hard in general but admit a closed form counting formula ?</p>
<p>PS:</p>
<ol>
<li>FO<span class="math-container">$^2$</span> admits model counting in polynomial time with respect to the domain elements, and also admits a closed form formula for counting.</li>
</ol>

CC BY-SA 4.0
2020-10-23T16:44:08.130Z
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.
Joshua Grochow
CC BY-SA 4.0
2021-01-13T19:42:52.187Z
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 https://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.
delete000
<counting-complexity><first-order-logic>
How does complexity of a counting problem influence wether it admits a closed form formula or not?
SagarM
# How does complexity of a counting problem influence wether it admits a closed form formula or not?

(Asked by: username_0 on 2020-10-22)

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.

**Tags:** counting-complexity, first-order-logic
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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 https://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.  

---

## 0 answers

