<p>So I put my afterthought that Emil refers to in his comment to the question in this answer in order to close this thread:</p>
<h4>Afterthoughts</h4>
<p>So I had the following idea of how to get around this problem: Instead of working with one TM <span class="math-container">$M'_N$</span> for every value of <span class="math-container">$N \in \{0, \dots, 2^{p(|x|)}\}$</span> we can make <span class="math-container">$N$</span> part of the input. In other words, we work with the TM <span class="math-container">$M'$</span> that takes as input the tuple <span class="math-container">$(N, x, u)$</span>. The language consisting of tuples <span class="math-container">$(N, x)$</span> where <span class="math-container">$|\{u \in \{0, 1\}^{p(|x| + 1)} : M'(N, x, u) = 1\}| \geq 2^{p(|x|)}$</span> is in <span class="math-container">$\mathrm{PP}$</span> and hence there is a polynomial-time TM for it assuming <span class="math-container">$\mathrm{PP} = \mathrm{P}$</span>. This single TM can be hardcoded in the TM that computes <span class="math-container">$f$</span>.</p>

CC BY-SA 4.0
2022-09-24T21:35:50.313Z
2022-09-24T21:35:50.313Z
sebastian
<h4>Introduction</h4>
<p>I am currently studying chapter 17 (of the famous textbook by Arora &amp; Barak [1]) on the complexity of counting and got stuck on the proof of Lemma 17.7, which states <span class="math-container">$\mathrm{PP} = \mathrm{P} \iff \#\mathrm{P} = \mathrm{FP}$</span>. I will first outline the proof and then formulate my question.</p>
<h4>Proof Outline</h4>
<p>The hard direction is proving <span class="math-container">$\mathrm{PP} = \mathrm{P} \implies \#\mathrm{P} = \mathrm{FP}$</span>. In other words, given a function <span class="math-container">$f \in \#P$</span> we want to show the existence of a polynomial-time TM that computes <span class="math-container">$f$</span> using the assumption <span class="math-container">$\mathrm{PP} = \mathrm{P}$</span>. Now since <span class="math-container">$f \in \#\mathrm{P}$</span>, by definition there exists a TM <span class="math-container">$M$</span> (and polynomial <span class="math-container">$p$</span>) such that <span class="math-container">$f(x) = |\{u \in \{0,  1\}^{p(|x|)} \, : \, M(x, u) = 1\}| := \#_M(x)$</span>. The main idea of the proof in the book is now as follows: For any natural number <span class="math-container">$N$</span>, we can build a polynomial-time TM <span class="math-container">$M'_N = M_N + M$</span> such that <span class="math-container">$\#_{M'_N}(x) := |\{u \in \{0,  1\}^{p(|x|) + 1} \, : \, M'_N(x, u) = 1\}| = N + \#_M(x)$</span>. Moreover, the assumption <span class="math-container">$\mathrm{P} = \mathrm{PP}$</span> yields the existence of a polynomial-time TM to decide whether <span class="math-container">$\#_{M'_N}(x) \geq 2^{p(|x|)}$</span>. Now if we find the smallest <span class="math-container">$N$</span> under which <span class="math-container">$\#_{M'_N}(x) \geq 2^{p(|x|)}$</span> is satisfied, we are done because we found <span class="math-container">$\#_M(x) = 2^{p(|x|)} - N$</span>. In the proof it is now claimed that this can be done using binary search.</p>
<h4>My struggles</h4>
<p>What I struggle with in this argument is the following: The goal of the proof is to show the existence of a polynomial-time TM that computes <span class="math-container">$f$</span>. According to the above proof, this TM works taking input <span class="math-container">$x$</span> and then running a binary search over <span class="math-container">$N \in \{0, \dots, 2^{p(|x|)} \}$</span>. For every <span class="math-container">$N$</span> in the search, our TM would have to simulate another polynomial-time TM that decides whether <span class="math-container">$\#_{M'_N}(x) \geq 2^{p(|x|)}$</span> or not. But we only know of the existence of these other TM's and there is one for every distinct value <span class="math-container">$N$</span> can take. In other words, our final TM would have to be able to first find the TM it has to simulate in every step of the binary search. It is not clear to me how this can be done and in particular, I don't see how the proof is complete without this information.</p>
<h4>Question</h4>
<p>So I guess my question is: Am I missing some obvious reason why this still works or is my reasoning flawed at some point? If not, how can we get around this issue?</p>
<p>[1] <em>Arora, Sanjeev; Barak, Boaz</em>, <a href="http://dx.doi.org/10.1017/CBO9780511804090" rel="nofollow noreferrer"><strong>Computational complexity. A modern approach.</strong></a>, Cambridge: Cambridge University Press (ISBN 978-0-521-42426-4/hbk). xxiv, 579 p. (2009). <a href="https://zbmath.org/?q=an:1193.68112" rel="nofollow noreferrer">ZBL1193.68112</a>.</p>

CC BY-SA 4.0
2022-09-24T07:23:48.767Z
Yes, your afterthought is correct.
Emil Jeřábek
CC BY-SA 4.0
2022-09-24T21:33:49.910Z
Cool, thanks for your comment, I'll close the question soon as I convinced myself of this now.
sebastian
<cc.complexity-theory><complexity-classes><counting-complexity><proofs>
On the proof of $PP = P \iff \#P = FP$ in Arora & Barak (Lemma 17.7)
sebastian
# On the proof of $PP = P \iff \#P = FP$ in Arora & Barak (Lemma 17.7)

(Asked by: username_0 on 2022-09-23)

#### Introduction

I am currently studying chapter 17 (of the famous textbook by Arora & Barak [1]) on the complexity of counting and got stuck on the proof of Lemma 17.7, which states $\mathrm{PP} = \mathrm{P} \iff \#\mathrm{P} = \mathrm{FP}$. I will first outline the proof and then formulate my question.

#### Proof Outline

The hard direction is proving $\mathrm{PP} = \mathrm{P} \implies \#\mathrm{P} = \mathrm{FP}$. In other words, given a function $f \in \#P$ we want to show the existence of a polynomial-time TM that computes $f$ using the assumption $\mathrm{PP} = \mathrm{P}$. Now since $f \in \#\mathrm{P}$, by definition there exists a TM $M$ (and polynomial $p$) such that $f(x) = |\{u \in \{0, 1\}^{p(|x|)} \, : \, M(x, u) = 1\}| := \#\_M(x)$. The main idea of the proof in the book is now as follows: For any natural number $N$, we can build a polynomial-time TM $M'\_N = M\_N + M$ such that $\#\_{M'\_N}(x) := |\{u \in \{0, 1\}^{p(|x|) + 1} \, : \, M'\_N(x, u) = 1\}| = N + \#\_M(x)$. Moreover, the assumption $\mathrm{P} = \mathrm{PP}$ yields the existence of a polynomial-time TM to decide whether $\#\_{M'\_N}(x) \geq 2^{p(|x|)}$. Now if we find the smallest $N$ under which $\#\_{M'\_N}(x) \geq 2^{p(|x|)}$ is satisfied, we are done because we found $\#\_M(x) = 2^{p(|x|)} - N$. In the proof it is now claimed that this can be done using binary search.

#### My struggles

What I struggle with in this argument is the following: The goal of the proof is to show the existence of a polynomial-time TM that computes $f$. According to the above proof, this TM works taking input $x$ and then running a binary search over $N \in \{0, \dots, 2^{p(|x|)} \}$. For every $N$ in the search, our TM would have to simulate another polynomial-time TM that decides whether $\#\_{M'\_N}(x) \geq 2^{p(|x|)}$ or not. But we only know of the existence of these other TM's and there is one for every distinct value $N$ can take. In other words, our final TM would have to be able to first find the TM it has to simulate in every step of the binary search. It is not clear to me how this can be done and in particular, I don't see how the proof is complete without this information.

#### Question

So I guess my question is: Am I missing some obvious reason why this still works or is my reasoning flawed at some point? If not, how can we get around this issue?

[1] *Arora, Sanjeev; Barak, Boaz*, [**Computational complexity. A modern approach.**](http://dx.doi.org/10.1017/CBO9780511804090), Cambridge: Cambridge University Press (ISBN 978-0-521-42426-4/hbk). xxiv, 579 p. (2009). [ZBL1193.68112](https://zbmath.org/?q=an:1193.68112).

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity, proofs
> **Comments:**
> **username_1**: Yes, your afterthought is correct.  
> **username_0**: Cool, thanks for your comment, I'll close the question soon as I convinced myself of this now.  

---

## 1 answers

### Answer by username_0 on 2022-09-24. Score: 1 | Accepted answer

So I put my afterthought that Emil refers to in his comment to the question in this answer in order to close this thread:

#### Afterthoughts

So I had the following idea of how to get around this problem: Instead of working with one TM $M'\_N$ for every value of $N \in \{0, \dots, 2^{p(|x|)}\}$ we can make $N$ part of the input. In other words, we work with the TM $M'$ that takes as input the tuple $(N, x, u)$. The language consisting of tuples $(N, x)$ where $|\{u \in \{0, 1\}^{p(|x| + 1)} : M'(N, x, u) = 1\}| \geq 2^{p(|x|)}$ is in $\mathrm{PP}$ and hence there is a polynomial-time TM for it assuming $\mathrm{PP} = \mathrm{P}$. This single TM can be hardcoded in the TM that computes $f$.


---

