patternMinor
Proof of $P^{\text{#}P} = P^{PP}$
Viewed 0 times
textproofstackoverflow
Problem
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.
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.
Solution
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:
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)$.
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:
- Guess a non-deterministic bit $b$.
- 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$.
- 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)$.
Context
StackExchange Computer Science Q#42725, answer score: 3
Revisions (0)
No revisions yet.