<p>Counting the models of propositional quantifier-free formulas, #SAT, is #P-complete (under parsimonious reductions).</p>
<p>I was wondering about the complexity of counting the models of existentially quantified formulas (∃x<sub>1</sub>…x<sub>n</sub> P), a problem known as <em>projected model counting</em>.</p>
<p>It's obviously #P-hard, obviously in PSPACE, and… I don't see to find anything in the literature.</p>

CC BY-SA 4.0
2022-02-07T14:14:51.647Z
Well, the problem is clearly #NP-complete. #NP is (along with all of $\mathrm{\#P^{ModPH}}$) included in $\mathrm{FP^{\#P[1]}}$; in fact, it is included in its subclass MP (see [The Power of the Middle Bit of a #P Function](https://doi.org/10.1006/jcss.1995.1036)), or rather, the function version of this class.
Emil Jeřábek
CC BY-SA 4.0
2022-02-07T14:19:18.307Z
Right about #NP-complete, but are there known equalities of classes there?
David Monniaux
CC BY-SA 4.0
2022-02-07T14:43:58.600Z
I don’t know of equalities as such, but as I wrote, this class is known to be just a tiny bit above #P: you can compute any #NP function by computing a #P function and throwing away a bunch of low-order and high-order bits. That’s quite a tight upper bound. Why do you need equalities?
Emil Jeřábek
CC BY-SA 4.0
2022-02-07T15:25:47.167Z
Actually I don't. Thanks for the references.
David Monniaux
<counting-complexity>
Complexity of projected model counting
David Monniaux
# Complexity of projected model counting

(Asked by: username_0 on 2022-02-07)

Counting the models of propositional quantifier-free formulas, #SAT, is #P-complete (under parsimonious reductions).

I was wondering about the complexity of counting the models of existentially quantified formulas (∃x1…xn P), a problem known as *projected model counting*.

It's obviously #P-hard, obviously in PSPACE, and… I don't see to find anything in the literature.

**Tags:** counting-complexity

> **Comments:**
> **username_1**: Well, the problem is clearly #NP-complete. #NP is (along with all of $\mathrm{\#P^{ModPH}}$) included in $\mathrm{FP^{\#P[1]}}$; in fact, it is included in its subclass MP (see [The Power of the Middle Bit of a #P Function](https://doi.org/10.1006/jcss.1995.1036)), or rather, the function version of this class.  
> **username_0**: Right about #NP-complete, but are there known equalities of classes there?  
> **username_1**: I don’t know of equalities as such, but as I wrote, this class is known to be just a tiny bit above #P: you can compute any #NP function by computing a #P function and throwing away a bunch of low-order and high-order bits. That’s quite a tight upper bound. Why do you need equalities?  
> **username_0**: Actually I don't. Thanks for the references.  

---

## 0 answers

