6

Following early discussion on 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.

David Monniaux
  • 1,122
  • 5
  • 16

1 Answers1

6

Theorem 4.1 (ii) in J. Torán, Complexity Classes defined by Counting Quantifiers: $\exists \mathsf{PP} = \mathsf{NP}^{\mathsf{\# P}}$ (and thus $= \mathsf{NP}^{\mathsf{PP}[1]}$).

I also have a short, propositional model theoretic proof of this, check it out.

Emil Jeřábek
  • 17,430
  • 3
  • 61
  • 90
David Monniaux
  • 1,122
  • 5
  • 16