2
$\begingroup$

I just discovered that a problem that I was studying could belong to $P^{PP}$, I would like to prove that this problem is $P^{PP}$-complete (if that is even a thing). The issue is that I'm unable to find any caracteristic problem that could be $P^{PP}$-complete.

Does anyone know any $P^{PP}$-complete problem? Or is it even ok to talk about hardness in $P^{PP}$?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ $\mathrm{P^{PP}}$-complete problems certainly exist, such as evaluation of Boolean circuits with MAJ-SAT (or #SAT) oracle gates. I do not know if there is something more natural. $\endgroup$
    – Emil Jeřábek
    Nov 25, 2022 at 20:31
  • 2
    $\begingroup$ I propose the following candidate for a $\mathrm{P^{PP}}$-complete problem: given a CNF $\phi$ in $n$ variables, output the least significant bit of the lexicographically first $a\in\{0,1\}^n$ such that $\bigl|\{x<_{\mathrm{Lex}}a:x\models\phi\}\bigr|\ge2^{n-1}$. $\endgroup$
    – Emil Jeřábek
    Nov 26, 2022 at 10:01
  • $\begingroup$ Could you send me a paper or place to check that problem, I can't seem to find anything about it $\endgroup$
    – AITOR GODOY
    Nov 28, 2022 at 9:30
  • $\begingroup$ I wrote that I propose this as a candidate complete problem. I do not know of any literature on the problem, or whether it has been considered by anyone, otherwise I would have posted a proper answer. $\endgroup$
    – Emil Jeřábek
    Nov 28, 2022 at 9:35
  • 2
    $\begingroup$ For any language $A$, evaluation of Boolean circuits with oracle $A$ is $P^A$-complete by the same argument as that the usual Circuit Value Problem is P-complete. You can find the latter in any number of places. $\endgroup$
    – Emil Jeřábek
    Nov 28, 2022 at 9:50

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy