<p>I developed this simple argument while learning about the <span class="math-container">$BP$</span> operator and McCreight and Meyer's Union Theorem, however I cannot pinpoint where my error is.</p>
<p>By the Union Theorem, there exists a total computable function <span class="math-container">$f$</span> such that <span class="math-container">$P = DTIME(f)$</span>. Therefore, <span class="math-container">$BPP = BP \cdot DTIME(f)$</span>, so <span class="math-container">$L \in BPP$</span> if and only if there is a deterministic verifier <span class="math-container">$V$</span> running in time <span class="math-container">$O(f)$</span> and a polynomial <span class="math-container">$h$</span> such that for all <span class="math-container">$x$</span>,
<span class="math-container">$$\Pr_{r \in \{0,1\}^{h(|x|)}}[V(x,r) = L(x)] \geq 2/3.$$</span>
Here, I underscore that by the definition of the <span class="math-container">$BP$</span> operator, <span class="math-container">$V$</span>'s runtime is a function of both <span class="math-container">$|x|$</span> and <span class="math-container">$|r|$</span>.</p>
<p>Now let <span class="math-container">$BP \cdot DTIME(g,h)$</span> consist of all languages <span class="math-container">$L$</span> for which there is a deterministic verifier <span class="math-container">$V$</span> running in time <span class="math-container">$O(g)$</span> (in both arguments) such that for all <span class="math-container">$x$</span>,
<span class="math-container">$$\Pr_{r \in \{0,1\}^{h(|x|)}}[V(x,r) = L(x)] \geq 2/3.$$</span></p>
<p><strong>Claim:</strong> If <span class="math-container">$P = BPP$</span>, then for every polynomial <span class="math-container">$h$</span>, <span class="math-container">$BPP = BP \cdot DTIME(f,h)$</span>.</p>
<p><em>Proof:</em> Basically, no randomness is needed, so in particular any amount of randomness will do.</p>
<p>Now consider the class <span class="math-container">$BPTIME(g, h)$</span>, which consists of all <span class="math-container">$L$</span> for which there is a deterministic verifier <span class="math-container">$V$</span> running in time <span class="math-container">$O(g)$</span> <em>in its first argument only</em> such that for all <span class="math-container">$x$</span>,
<span class="math-container">$$\Pr_{r \in \{0,1\}^{h(|x|)}}[V(x,r) = L(x)] \geq 2/3.$$</span>
Here, I underscore that <span class="math-container">$V(x,r)$</span> runs in time <span class="math-container">$O(g(|x|))$</span>, <em>not</em> <span class="math-container">$O(g(|x| + |r|))$</span>. The reason for this is because <span class="math-container">$BPTIME(g)$</span> is canonically defined relative to a probabilistic Turing machine that runs in time <span class="math-container">$O(g(|x|))$</span>. Thus, translating this definition to use a deterministic machine entails that the runtime remains strictly a function of <span class="math-container">$|x|$</span>, and not of the number of random bits.</p>
<p>Defining, for all <span class="math-container">$n$</span>, <span class="math-container">$h'(n) = h(n) + n$</span>, it is easy to prove the following:</p>
<p><strong>Claim:</strong> <span class="math-container">$BP \cdot DTIME(g,h) = BPTIME(g \circ h', h)$</span>.</p>
<p>Therefore, by the above Claims, if <span class="math-container">$P = BPP$</span>, then, for every polynomial <span class="math-container">$h$</span>,
<span class="math-container">$$P = DTIME(f) = BPP = BP \cdot DTIME(f,h) = BPTIME(f \circ h', h).$$</span> But evidently, <span class="math-container">$DTIME(f) \subseteq DTIME(f \circ h) \subseteq BPTIME(f \circ h', h)$</span>, and so we conclude that <span class="math-container">$DTIME(f) = DTIME(f \circ h)$</span> for every polynomial <span class="math-container">$h$</span>, which violates the Time Hierarchy Theorem.</p>
<p>Where is the mistake?</p>

CC BY-SA 4.0
2023-12-11T18:31:33.657Z
The last line doesn't violate the Time Hierarchy Theorem because the f from the Union Theorem is not time-constructible, but the Time Hierarchy Theorem requires its runtimes to be time-constructible.
Joshua Grochow
CC BY-SA 4.0
2023-12-11T18:35:52.877Z
Right! Thanks @JoshuaGrochow.
trillianhaze
CC BY-SA 4.0
2023-12-11T19:21:17.053Z
In fact, P = BPP is a red herring here, isn’t it? You can get $\mathrm{DTIME}(f)=\mathrm{DTIME}(f\circ h)$ for all polynomials $h(n)\ge n$ unconditionally by a simple paddding argument.
Emil Jeřábek
<cc.complexity-theory><complexity-classes><proofs>
What's wrong with this $P \neq BPP$ proof?
trillianhaze
# What's wrong with this $P \neq BPP$ proof?

(Asked by: username_0 on 2023-12-11)

I developed this simple argument while learning about the $BP$ operator and McCreight and Meyer's Union Theorem, however I cannot pinpoint where my error is.

By the Union Theorem, there exists a total computable function $f$ such that $P = DTIME(f)$. Therefore, $BPP = BP \cdot DTIME(f)$, so $L \in BPP$ if and only if there is a deterministic verifier $V$ running in time $O(f)$ and a polynomial $h$ such that for all $x$,
$$\Pr\_{r \in \{0,1\}^{h(|x|)}}[V(x,r) = L(x)] \geq 2/3.$$
Here, I underscore that by the definition of the $BP$ operator, $V$'s runtime is a function of both $|x|$ and $|r|$.

Now let $BP \cdot DTIME(g,h)$ consist of all languages $L$ for which there is a deterministic verifier $V$ running in time $O(g)$ (in both arguments) such that for all $x$,
$$\Pr\_{r \in \{0,1\}^{h(|x|)}}[V(x,r) = L(x)] \geq 2/3.$$

**Claim:** If $P = BPP$, then for every polynomial $h$, $BPP = BP \cdot DTIME(f,h)$.

*Proof:* Basically, no randomness is needed, so in particular any amount of randomness will do.

Now consider the class $BPTIME(g, h)$, which consists of all $L$ for which there is a deterministic verifier $V$ running in time $O(g)$ *in its first argument only* such that for all $x$,
$$\Pr\_{r \in \{0,1\}^{h(|x|)}}[V(x,r) = L(x)] \geq 2/3.$$
Here, I underscore that $V(x,r)$ runs in time $O(g(|x|))$, *not* $O(g(|x| + |r|))$. The reason for this is because $BPTIME(g)$ is canonically defined relative to a probabilistic Turing machine that runs in time $O(g(|x|))$. Thus, translating this definition to use a deterministic machine entails that the runtime remains strictly a function of $|x|$, and not of the number of random bits.

Defining, for all $n$, $h'(n) = h(n) + n$, it is easy to prove the following:

**Claim:** $BP \cdot DTIME(g,h) = BPTIME(g \circ h', h)$.

Therefore, by the above Claims, if $P = BPP$, then, for every polynomial $h$,
$$P = DTIME(f) = BPP = BP \cdot DTIME(f,h) = BPTIME(f \circ h', h).$$ But evidently, $DTIME(f) \subseteq DTIME(f \circ h) \subseteq BPTIME(f \circ h', h)$, and so we conclude that $DTIME(f) = DTIME(f \circ h)$ for every polynomial $h$, which violates the Time Hierarchy Theorem.

Where is the mistake?

**Tags:** cc.complexity-theory, complexity-classes, proofs
> **Comments:**
> **username_1**: The last line doesn't violate the Time Hierarchy Theorem because the f from the Union Theorem is not time-constructible, but the Time Hierarchy Theorem requires its runtimes to be time-constructible.  
> **username_0**: Right! Thanks @JoshuaGrochow.  
> **username_2**: In fact, P = BPP is a red herring here, isn’t it? You can get $\mathrm{DTIME}(f)=\mathrm{DTIME}(f\circ h)$ for all polynomials $h(n)\ge n$ unconditionally by a simple paddding argument.  

---

## 0 answers

