Complexity of maximizing the number of models in a parametric formula

Question

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.

I have no idea. Comparison "greater than $N$" seems a bit weak for that to be true. — David Monniaux, Jan 30 '22 at 08: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}}$. — Emil Jeřábek, Jan 30 '22 at 09:30
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, Jan 30 '22 at 09:59
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, Jan 31 '22 at 08:14
Are there any results known about $\mathrm{NP}^{\mathrm{PP}[1]}$? — David Monniaux, Jan 31 '22 at 11:27

score 2 · Answer 1 · answered Feb 24 '22 at 18:02

2

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

answered Feb 24 '22 at 18:02

David Monniaux

1,122
5
16

Complexity of maximizing the number of models in a parametric formula

1 Answers1

Linked