<p>I just discovered that a problem that I was studying could belong to <span class="math-container">$P^{PP}$</span>, I would like to prove that this problem is <span class="math-container">$P^{PP}$</span>-complete (if that is even a thing). The issue is that I'm unable to find any caracteristic problem that could be <span class="math-container">$P^{PP}$</span>-complete.</p>
<p>Does anyone know any <span class="math-container">$P^{PP}$</span>-complete problem? Or is it even ok to talk about hardness in <span class="math-container">$P^{PP}$</span>?</p>

CC BY-SA 4.0
2022-11-25T20:31:28.093Z
$\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.
Emil Jeřábek
CC BY-SA 4.0
2022-11-26T10:01:46.023Z
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}$.
Emil Jeřábek
CC BY-SA 4.0
2022-11-28T09:30:57.997Z
Could you send me a paper or place to check that problem, I can't seem to find anything about it
AITOR GODOY
CC BY-SA 4.0
2022-11-28T09:35:18.233Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-11-28T09:37:57.957Z
I meant about the evaluation of Boolean circuits with MAJ-SAT.
AITOR GODOY
CC BY-SA 4.0
2022-11-28T09:50:58.803Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-11-28T10:16:41.260Z
Oh ok, I understand now, thank you.
AITOR GODOY
<cc.complexity-theory><complexity-classes><counting-complexity>
Problems in $P^{PP}$
AITOR GODOY
# Problems in $P^{PP}$

(Asked by: username_0 on 2022-11-25)

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

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity
> **Comments:**
> **username_1**: $\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.  
> **username_1**: 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}$.  
> **username_0**: Could you send me a paper or place to check that problem, I can't seem to find anything about it  
> **username_1**: 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.  
> **username_0**: I meant about the evaluation of Boolean circuits with MAJ-SAT.  
> **username_1**: 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.  
> **username_0**: Oh ok, I understand now, thank you.  

---

## 0 answers

