<p>The decision problem is <span class="math-container">$\exists \mathsf{PP}$</span>-complete and this class is equal to <span class="math-container">$\mathsf{NP}^{\#\mathsf{P}}$</span>. See <a href="https://cstheory.stackexchange.com/questions/51050/what-is-known-about-mathrmnp-mathrmpp1">this post</a> and <a href="https://hal.archives-ouvertes.fr/hal-03586193v1" rel="nofollow noreferrer">this preprint</a>.</p>

CC BY-SA 4.0
2022-02-24T18:02:58.420Z
2022-02-24T18:02:58.420Z
David Monniaux
<p>Let <span class="math-container">$F(x,y)$</span> be a propositional formula where <span class="math-container">$x$</span> and <span class="math-container">$y$</span> are vectors of Booleans. We want to maximize over <span class="math-container">$x$</span> the number of models of <span class="math-container">$F$</span> over <span class="math-container">$y$</span>. As a decision problem, this becomes: given <span class="math-container">$F(x,y)$</span> and <span class="math-container">$N$</span>, is there an <span class="math-container">$x$</span> such that the number of <span class="math-container">$y$</span> such that <span class="math-container">$F(x,y)$</span> exceeds <span class="math-container">$N$</span> — <span class="math-container">$\#\{y \mid F(x,y)\} \geq N$</span>.</p>
<p>This problem is in <span class="math-container">$\mathrm{NP}^{\#\mathrm{P}}$</span>, but I have not found it discussed in the literature. There are a few old posts here (<a href="https://cstheory.stackexchange.com/questions/20119/do-we-know-whether-pp-npp">Do we know whether P^#P = NP^#P?</a>, <a href="https://cstheory.stackexchange.com/questions/2559/is-conp-p-np-p-p-p">Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?</a>) that discuss possible relations between <span class="math-container">$\mathrm{P}^{\#\mathrm{P}}$</span> and <span class="math-container">$\mathrm{NP}^{\#\mathrm{P}}$</span>, but nothing much conclusive.</p>
<p>I'm wondering if this problem has a name and if there are results on it.</p>

CC BY-SA 4.0
2022-01-30T02:49:44.737Z
Is the problem complete for $\text{NP}^\text{#P}$?
Neal Young
CC BY-SA 4.0
2022-01-30T08:01:49.543Z
I have no idea. Comparison "greater than $N$" seems a bit weak for that to be true.
David Monniaux
CC BY-SA 4.0
2022-01-30T09:30:09.053Z
The decision problem is in $\mathrm{\exists PP=NP^{PP[1]}}$. This might well be a strict subclass of $\mathrm{NP^{\#P}=NP^{PP}}$.
Emil Jeřábek
CC BY-SA 4.0
2022-01-30T09:59:49.743Z
Notation issue: is $\mathrm{X}^{Y[1]}$ the class where $X$ is allowed to make only a single call to $Y$ during one execution?
David Monniaux
CC BY-SA 4.0
2022-01-30T20:28:29.200Z
I'm thinking it is $\mathrm{NP}^{\mathrm{PP}[1]}$-complete.
David Monniaux
CC BY-SA 4.0
2022-01-31T08:14:55.493Z
Yes, that’s what the notation means. And I think you are right, the problem looks like it is $\mathrm{NP^{PP[1]}}$-complete.
Emil Jeřábek
CC BY-SA 4.0
2022-01-31T11:27:02.220Z
Are there any results known about $\mathrm{NP}^{\mathrm{PP}[1]}$?
David Monniaux
<sat><counting-complexity>
Complexity of maximizing the number of models in a parametric formula
David Monniaux
# Complexity of maximizing the number of models in a parametric formula

(Asked by: username_0 on 2022-01-29)

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?](https://cstheory.stackexchange.com/questions/20119/do-we-know-whether-pp-npp), [Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?](https://cstheory.stackexchange.com/questions/2559/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.

**Tags:** sat, counting-complexity
> **Comments:**
> **username_1**: Is the problem complete for $\text{NP}^\text{#P}$?  
> **username_0**: I have no idea. Comparison "greater than $N$" seems a bit weak for that to be true.  
> **username_2**: The decision problem is in $\mathrm{\exists PP=NP^{PP[1]}}$. This might well be a strict subclass of $\mathrm{NP^{\#P}=NP^{PP}}$.  
> **username_0**: Notation issue: is $\mathrm{X}^{Y[1]}$ the class where $X$ is allowed to make only a single call to $Y$ during one execution?  
> **username_0**: I'm thinking it is $\mathrm{NP}^{\mathrm{PP}[1]}$-complete.  
> **username_2**: Yes, that’s what the notation means. And I think you are right, the problem looks like it is $\mathrm{NP^{PP[1]}}$-complete.  
> **username_0**: Are there any results known about $\mathrm{NP}^{\mathrm{PP}[1]}$?  

---

## 1 answers

### Answer by username_0 on 2022-02-24. Score: 2

The decision problem is $\exists \mathsf{PP}$-complete and this class is equal to $\mathsf{NP}^{\#\mathsf{P}}$. See [this post](https://cstheory.stackexchange.com/questions/51050/what-is-known-about-mathrmnp-mathrmpp1) and [this preprint](https://hal.archives-ouvertes.fr/hal-03586193v1).


---

