<p>Theorem 4.1 (ii) in J. Torán, <a href="https://dl.acm.org/doi/abs/10.1145/116825.116858" rel="nofollow noreferrer"><em>Complexity Classes defined by Counting Quantifiers</em></a>: <span class="math-container">$\exists \mathsf{PP} = \mathsf{NP}^{\mathsf{\# P}}$</span> (and thus <span class="math-container">$= \mathsf{NP}^{\mathsf{PP}[1]}$</span>).</p>
<p>I also have a short, propositional model theoretic <a href="https://hal.archives-ouvertes.fr/hal-03586193" rel="nofollow noreferrer">proof</a> of this, check it out.</p>

CC BY-SA 4.0
2022-02-22T14:01:01.770Z
@davidmonniux can you provide your proof?
Turbo
CC BY-SA 4.0
2022-02-24T08:24:28.890Z
Done. Feel free to comment.
David Monniaux
CC BY-SA 4.0
2022-02-22T07:17:37.800Z
2022-02-24T08:38:01.027Z
2022-02-24T08:38:01.027Z
David Monniaux
<p>Following early discussion on <a href="https://cstheory.stackexchange.com/questions/51043/complexity-of-maximizing-the-number-of-models-in-a-parametric-formula">Complexity of maximizing the number of models in a parametric formula</a> it seems that the problem discussed is equivalent to a complete problem in <span class="math-container">$\mathrm{NP}^{\mathrm{PP}[1]}$</span>, that is, the class of problems solvable in nondeterministic polynomial time with at most one call to a <span class="math-container">$\mathrm{PP}$</span> oracle (a <span class="math-container">$\mathrm{PP}$</span> oracle accepts if at least half of its nondeterministically possible runs accept).</p>
<p>I've not seen this class mentioned in the literature, but I probably missed something. I was wondering what is known about it.</p>

<counting-complexity>
What is known about $\mathrm{NP}^{\mathrm{PP}[1]}$?
David Monniaux
# What is known about $\mathrm{NP}^{\mathrm{PP}[1]}$?

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

Following early discussion on [Complexity of maximizing the number of models in a parametric formula](https://cstheory.stackexchange.com/questions/51043/complexity-of-maximizing-the-number-of-models-in-a-parametric-formula) it seems that the problem discussed is equivalent to a complete problem in $\mathrm{NP}^{\mathrm{PP}[1]}$, that is, the class of problems solvable in nondeterministic polynomial time with at most one call to a $\mathrm{PP}$ oracle (a $\mathrm{PP}$ oracle accepts if at least half of its nondeterministically possible runs accept).

I've not seen this class mentioned in the literature, but I probably missed something. I was wondering what is known about it.

**Tags:** counting-complexity


---

## 1 answers

### Answer by username_0 on 2022-02-22. Score: 6

Theorem 4.1 (ii) in J. Torán, [*Complexity Classes defined by Counting Quantifiers*](https://dl.acm.org/doi/abs/10.1145/116825.116858): $\exists \mathsf{PP} = \mathsf{NP}^{\mathsf{\# P}}$ (and thus $= \mathsf{NP}^{\mathsf{PP}[1]}$).

I also have a short, propositional model theoretic [proof](https://hal.archives-ouvertes.fr/hal-03586193) of this, check it out.

> **Comments:**
> **username_1**: @davidmonniux can you provide your proof?  
> **username_0**: Done. Feel free to comment.  

---

