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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

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

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.