6
$\begingroup$

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.

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

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.