# Complexity of maximizing the number of models in a parametric formula

Let $$F(x,y)$$ be a propositional formula where $$x$$ and $$y$$ are vectors of Booleans. We want to maximize over $$x$$ the number of models of $$F$$ over $$y$$. As a decision problem, this becomes: given $$F(x,y)$$ and $$N$$, is there an $$x$$ such that the number of $$y$$ such that $$F(x,y)$$ exceeds $$N$$$$\#\{y \mid F(x,y)\} \geq N$$.

This problem is in $$\mathrm{NP}^{\#\mathrm{P}}$$, but I have not found it discussed in the literature. There are a few old posts here (Do we know whether P^#P = NP^#P?, Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?) that discuss possible relations between $$\mathrm{P}^{\#\mathrm{P}}$$ and $$\mathrm{NP}^{\#\mathrm{P}}$$, but nothing much conclusive.

I'm wondering if this problem has a name and if there are results on it.

• Is the problem complete for $\text{NP}^\text{#P}$? Jan 30, 2022 at 2:49
• I have no idea. Comparison "greater than $N$" seems a bit weak for that to be true. Jan 30, 2022 at 8:01
• The decision problem is in $\mathrm{\exists PP=NP^{PP[1]}}$. This might well be a strict subclass of $\mathrm{NP^{\#P}=NP^{PP}}$. Jan 30, 2022 at 9:30
• I'm thinking it is $\mathrm{NP}^{\mathrm{PP}[1]}$-complete. Jan 30, 2022 at 20:28
• Yes, that’s what the notation means. And I think you are right, the problem looks like it is $\mathrm{NP^{PP[1]}}$-complete. Jan 31, 2022 at 8:14

The decision problem is $$\exists \mathsf{PP}$$-complete and this class is equal to $$\mathsf{NP}^{\#\mathsf{P}}$$. See this post and this preprint.