<p>For a simple problem in <span class="math-container">$\mathrm{P^{PP}}$</span> that’s presumably not in <span class="math-container">$\mathrm{PP}$</span>: given a 3CNF <span class="math-container">$\phi$</span> in <span class="math-container">$n$</span> variables, determine the <span class="math-container">$\lfloor n/2\rfloor$</span>-th bit of <span class="math-container">$|\{\vec a\in\{0,1\}^n:\phi(\vec a)=1\}|$</span>. This is (presumably) not <span class="math-container">$\mathrm{P^{PP}}$</span>-complete, though; it is complete for the class <span class="math-container">$\mathrm{MP\subseteq P^{PP}}$</span>.</p>
<p>I don’t know if there is something more natural, but the following problem is easily shown to be <span class="math-container">$\mathrm{P^{PP}}$</span>-complete: given a sequence of CNF
<span class="math-container">$$\phi_0(\vec x),\phi_1(\vec x,y_0),\dots,\phi_i(\vec x,y_0,\dots,y_{i-1}),\dots,\phi_n(\vec x,y_0,\dots,y_{n-1}),$$</span>
determine <span class="math-container">$b_n$</span>, where <span class="math-container">$(b_0,\dots,b_n)\in\{0,1\}^{n+1}$</span> is the unique sequence such that
<span class="math-container">$$b_i=1\iff\Pr\nolimits_{\vec a}[\phi_i(\vec a,b_0,\dots,b_{i-1})=1]\ge1/2$$</span>
for each <span class="math-container">$i\le n$</span>.</p>

CC BY-SA 4.0
2023-07-04T11:23:37.597Z
thank you. I understood the 1st problem. the second one though I am struggling a bit (too condensed a notation). If possible can you please elaborate the second one. Or provide a link where its explained?
J.Doe
CC BY-SA 4.0
2023-07-04T11:36:07.647Z
I’m sorry, but I can’t elaborate if you don’t tell me what exactly you struggle with. I have no link, as I just thought it up. If one sees a dozen of completeness proofs for problems like this, one can invent the next one.
Emil Jeřábek
CC BY-SA 4.0
2023-07-04T11:46:54.633Z
I understood that we calculate $b_i$ using previous values of $b_0, b_1...$ and so on, but am not clear how: $b_i=1\iff\Pr\nolimits_{\vec a}[\phi_i(\vec a,b_0,\dots,b_{i-1})=1]\ge1/2.$ This part is what I am struggling with. Are we saying that each successive CNF takes 1 extra 'bit/input' and its hard-coded value is the previous $b_{i-1}$. And if with these hard-coded bits the $\phi_i$ is satiable for more than 1/2 the cases the value of $b_i$=1 which is used for the next CNF and so on?
J.Doe
CC BY-SA 4.0
2023-07-04T12:28:14.223Z
Yes. As indicated at the beginning, $\phi_i$ has variables $\vec x,y_0,\dots,y_{i-1}$. We evaluate $y_j$, $j<i$, with the already known values $b_j$, and we ask whether the formula is satisfied by at least half of the assignments to the remaining variables $\vec x$.
Emil Jeřábek
CC BY-SA 4.0
2023-07-04T12:31:53.213Z
I added a generic element of the input sequence to hopefully make this more clear.
Emil Jeřábek
CC BY-SA 4.0
2023-07-04T12:37:15.257Z
thank you for clarifying..
J.Doe
CC BY-SA 4.0
2023-07-04T10:48:28.460Z
2023-07-04T12:31:04.127Z
2023-07-04T12:31:04.127Z
Emil Jeřábek
<p>Can someone provide an example of (possibly complete) natural problems in the class <span class="math-container">$P^{PP}$</span>?</p>
<p>we know that <strong>MAJSAT</strong> is a <span class="math-container">$PP$</span> complete problem which is defined as: Given a Boolean formula <strong>F</strong>. The answer must be YES if more than half of all assignments <span class="math-container">$x_1$</span>, <span class="math-container">$x_2$</span>, ..., <span class="math-container">$x_n$</span> make <strong>F</strong> TRUE and NO otherwise.</p>

<cc.complexity-theory>
Example of a problem in $P^{PP}$?
J.Doe
# Example of a problem in $P^{PP}$?

(Asked by: username_0 on 2023-07-04)

Can someone provide an example of (possibly complete) natural problems in the class $P^{PP}$?

we know that **MAJSAT** is a $PP$ complete problem which is defined as: Given a Boolean formula **F**. The answer must be YES if more than half of all assignments $x\_1$, $x\_2$, ..., $x\_n$ make **F** TRUE and NO otherwise.

**Tags:** cc.complexity-theory

---

## 1 answers

### Answer by username_1 on 2023-07-04. Score: 7 | Accepted answer

For a simple problem in $\mathrm{P^{PP}}$ that’s presumably not in $\mathrm{PP}$: given a 3CNF $\phi$ in $n$ variables, determine the $\lfloor n/2\rfloor$-th bit of $|\{\vec a\in\{0,1\}^n:\phi(\vec a)=1\}|$. This is (presumably) not $\mathrm{P^{PP}}$-complete, though; it is complete for the class $\mathrm{MP\subseteq P^{PP}}$.

I don’t know if there is something more natural, but the following problem is easily shown to be $\mathrm{P^{PP}}$-complete: given a sequence of CNF
$$\phi\_0(\vec x),\phi\_1(\vec x,y\_0),\dots,\phi\_i(\vec x,y\_0,\dots,y\_{i-1}),\dots,\phi\_n(\vec x,y\_0,\dots,y\_{n-1}),$$
determine $b\_n$, where $(b\_0,\dots,b\_n)\in\{0,1\}^{n+1}$ is the unique sequence such that
$$b\_i=1\iff\Pr\nolimits\_{\vec a}[\phi\_i(\vec a,b\_0,\dots,b\_{i-1})=1]\ge1/2$$
for each $i\le n$.

> **Comments:**
> **username_0**: thank you. I understood the 1st problem. the second one though I am struggling a bit (too condensed a notation). If possible can you please elaborate the second one. Or provide a link where its explained?  
> **username_1**: I’m sorry, but I can’t elaborate if you don’t tell me what exactly you struggle with. I have no link, as I just thought it up. If one sees a dozen of completeness proofs for problems like this, one can invent the next one.  
> **username_0**: I understood that we calculate $b_i$ using previous values of $b_0, b_1...$ and so on, but am not clear how: $b_i=1\iff\Pr\nolimits_{\vec a}[\phi_i(\vec a,b_0,\dots,b_{i-1})=1]\ge1/2.$ This part is what I am struggling with. Are we saying that each successive CNF takes 1 extra 'bit/input' and its hard-coded value is the previous $b_{i-1}$. And if with these hard-coded bits the $\phi_i$ is satiable for more than 1/2 the cases the value of $b_i$=1 which is used for the next CNF and so on?  
> **username_1**: Yes. As indicated at the beginning, $\phi_i$ has variables $\vec x,y_0,\dots,y_{i-1}$. We evaluate $y_j$, $j<i$, with the already known values $b_j$, and we ask whether the formula is satisfied by at least half of the assignments to the remaining variables $\vec x$.  
> **username_1**: I added a generic element of the input sequence to hopefully make this more clear.  
> **username_0**: thank you for clarifying..  

---

