# What's wrong with this $P \neq BPP$ proof?

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?

• 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. Dec 11, 2023 at 18:31
• Right! Thanks @JoshuaGrochow. Dec 11, 2023 at 18:35
• 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. Dec 11, 2023 at 19:21