3
$\begingroup$

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.

$\endgroup$

1 Answer 1

5
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – J.Doe
    Jul 4, 2023 at 11:23
  • $\begingroup$ 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. $\endgroup$ Jul 4, 2023 at 11:36
  • $\begingroup$ 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? $\endgroup$
    – J.Doe
    Jul 4, 2023 at 11:46
  • 1
    $\begingroup$ 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$. $\endgroup$ Jul 4, 2023 at 12:28
  • $\begingroup$ I added a generic element of the input sequence to hopefully make this more clear. $\endgroup$ Jul 4, 2023 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.