# Example of a problem in $P^{PP}$?

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.

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$$.
• 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? Jul 4, 2023 at 11:46
• 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$. Jul 4, 2023 at 12:28