1
$\begingroup$

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.
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Oct 23 '20 at 16:44
  • $\begingroup$ 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. $\endgroup$ – delete000 Jan 13 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.