6
$\begingroup$

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.

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @davidmonniux can you provide your proof? $\endgroup$
    – Turbo
    Commented Feb 22, 2022 at 14:01
  • $\begingroup$ Done. Feel free to comment. $\endgroup$ Commented Feb 24, 2022 at 8:24

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.