# Problems in $P^{PP}$

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}$$?

• $\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. Commented Nov 25, 2022 at 20:31
• 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}$. Commented Nov 26, 2022 at 10:01
• Could you send me a paper or place to check that problem, I can't seem to find anything about it Commented Nov 28, 2022 at 9:30
• 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. Commented Nov 28, 2022 at 9:35
• 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. Commented Nov 28, 2022 at 9:50