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.

$\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$ 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$ Jan 30, 2022 at 9:30
  • 1
    $\begingroup$ I'm thinking it is $\mathrm{NP}^{\mathrm{PP}[1]}$-complete. $\endgroup$ 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$ Jan 31, 2022 at 8:14

1 Answer 1

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.

$\endgroup$

Your Answer

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

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