3
$\begingroup$

I was reading this article on the complexity class $PP$.

In the fourth paragraph there is a claim that $P^{\text{#}P} = P^{PP}$ and that it can be proved using binary search. Can anyone please explain this in better detail?
The author himself gives the following explanation: If $f$ is a $\text{#P}$ function then the language $L= {(x,k) | f(x) \geq k}$ is in $PP$. Then do binary search on $k$.

This is still not clear to me. The other direction, $P^{PP} \subseteq P^{\text{#}P}$ is clear.

$\endgroup$
  • 1
    $\begingroup$ Please do not post the same question on multiple sites. It violates site rules. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration. I recommend that you pick which site you think is more suitable for your question, and delete the other copy. $\endgroup$ – D.W. May 18 '15 at 22:22
  • $\begingroup$ P.S. I see you were previously requested not to cross-post. I realize that was almost a month ago, so you might have forgotten, but just wanted to share a reminder. $\endgroup$ – D.W. May 18 '15 at 22:26
  • $\begingroup$ @D.W. I do appreciate people spending their time to answer and in no way do I intend to make them waste their time. I have given the link to the same question on the other site so that one could check the other site before answering $\endgroup$ – user23522 May 18 '15 at 22:39
  • $\begingroup$ rookie, cross-posting is forbidden, even if you give a link to the other site where you cross-posted. See the link in my first comment. You have an opportunity to choose for yourself which site is more suitable for your question, after reading the help center at both sites. If you don't take that opportunity, the moderators might choose for you. $\endgroup$ – D.W. May 18 '15 at 22:43
2
$\begingroup$

It all boils down to simulating a $\mathsf{\# P}$ oracle using a $\mathsf{PP}$ oracle. Consider a $\mathsf{\# P}$ oracle call: a polytime non-deterministic Turing machine $T$ and an input $x$. We want to know how many runs of $T$ result in the output $1$. Denote this number by $T_1(x)$, and denote the total number of runs of $T$ on $x$ by $T(x)$.

First, let's show that using a $\mathsf{PP}$ oracle we can decide whether $T(x) \geq y$ for any polysize $y$. We construct a Turing machine $T'$ that acts as follows:

  1. Guess a non-deterministic bit $b$.
  2. If $b = 0$, then simulate $T$ on $x$ in such a way that there are $2T(x)+1$ different paths, and in all of them return $1$.
  3. If $b = 1$, then have $2y$ different paths, all of them returning $0$.

The $\mathsf{PP}$ oracle returns Yes iff $T(x) \geq y$. I'll let you show how to implement steps 2 and 3.

Second, we can use binary search to determine $T(x)$ exactly. We start by determining some upper bound on $T(x)$: ask whether $T(x) \geq 2^k$ for $k=0,1,\ldots$, until you find a value of $k$ such that $T(x) < 2^k$. Since $T$ runs in polytime, $k$ is polynomial, and so this step takes polytime. Next, you do classical binary search (starting from $0 \leq T(x) < 2^k$), and determine $T(x)$ exactly. Again, this takes polytime since $k$ is polynomial.

Third, using our knowledge of $T(x)$, we can decide whether $T_1(x) \geq y$ in a similar way. For example, we could construct a new machine $T'$ with $T'(x) = T(x) + T_1(x)$, and then decide whether $T'(x) \geq T(x) + y$. You fill in the details.

Finally, we calculate $T_1(x)$ using binary search. This time we can skip the first half-step since we already know that $T_1(x) \leq T(x)$.

$\endgroup$
  • $\begingroup$ Step 2: add 2 children to each of the leaf nodes in the computation tree of T. Then add 2 children to any one of the (new)leaf. And make each one an accept node. Is this how it is? But step 3? Could you please elaborate the solution a liitle more? $\endgroup$ – user23522 May 19 '15 at 0:59
  • $\begingroup$ There are many ways of implementing step 2 and step 3. Please spend a few hours thinking about this, and only if you're still stuck, come back here. $\endgroup$ – Yuval Filmus May 19 '15 at 1:00
  • $\begingroup$ We can only determine $T(x) \geq y$ for polysize $y$, right? How can we determine $T(x) \geq 2^k$; $2^k$ need not be poly(|x|). $\endgroup$ – user23522 May 20 '15 at 6:40
  • $\begingroup$ It's not $y$ but $|y|$ (the length of the binary encoding of $y$) that needs to be polysize. $\endgroup$ – Yuval Filmus May 20 '15 at 6:52
  • $\begingroup$ Got it. And the classical binary search for $T(x)$ part. Once we have determined the smallest $k$ for which $T(x)<2^k$, the search can be restricted to $[2^{k-1} , 2^k ]$ range, that is we don't have to start with $[0, 2^k)$ range, right? $\endgroup$ – user23522 May 20 '15 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy