5
$\begingroup$

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?

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.