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$
  • 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 at 16:44

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.