7.4

Run the machine $M$ for sufficiently many times and accepts iff in one of the runs $M$ accepts.

7.5

Under Construction

7.6

(a)

Suppose $M'$ is the $\ZPP$ TM for $L$. For the first direction, we could set a polynomial time limit. We output whatever $M$ outputs if $M$ halts and ? otherwise. For the other direction, we run $M$ until it outputs something other than ?. We could prove that the expected time is indeed polynomial.

(b)

Using the result in (a), there is a PTM that runs in fixed polynomial time. More importantly, the PTM is guaranteed to output the correct answer every time. We could design a machine $M$ that runs the PTM for some rounds, outputs whatever it outputs. If its outputs are all ? for every round of running, $M$ outputs 0 or 1 at random. $M$ is a PTM that satisfies both the definition for $\RP$ and that for $\coRP$.

7.7

Proof. First of all, apparently $3\SAT \in \NPpoly$ since verifying a $3\SAT$ problem is in $\P$ and $\P \subseteq \Ppoly$, which means we could use a poly-sized circuit to verify a $3\SAT$ expression. Next, we show that we could constuct a poly-sized circuit for any $L \in \BPNP$.

We know that $\forall L \in \BPNP$, there is a PTM $M$ that runs in poly-time such that $\forall x, \prob{r \in \{0,1\}^m}{L(x) = 3\SAT(M(x,r))} \ge \frac23$, in which $m = p(\|x\|)$ (alternative definition). Denote by $n$ the length of $x$. With the error reduction technique, we could assume that $M$ satisfies

\[\forall x, \prob{r \in \{0, 1\}^m}{L(x) = 3\SAT(M(x, r))} \ge 1 - 2^{-n}\]

Thus, by the union bound, we know that there could be at most $2^{m-n} \le 2^{m-1}$ possible $r$’s that make the two differ. However, there are in total $2^m$ possible strings of $r$, which indicates the existance of a $r_n$ that satisfies $\forall x, L(x) = 3\SAT(M(x, r_n))$. Since evaluating $M(x, r_n)$ only takes a poly-sized circuit, for each $x \in L$, we could construct such a circuit that first evaluates $M(x, r_n)$, then verify that this string is in $3\SAT$.

Thus, we have that $\BPNP \subseteq \NPpoly \tag*{$\blacksquare$}$.

7.8

Under Construction

7.9

Proof. For any $L \in \BPL$, there is a PTM $M$ using logarithmic space deciding $L$. Since $M$ only uses logarithmic space, the number of its configurations, $N$, is at most polynomial in terms of the input length. We could first calculate a $N \times N$ matrix $A$ such that

\[A(C_i, C_j) = \left\{ \begin{array}{cc} \frac12 & \langle C_i, C_j \rangle\text{ is a valid transition in }M\\ 0 & \text{otherwise} \end{array} \right.\]

We could then compute $(A + I)^t$ to get the probability of each each transition to happen after time $t$. Thus, we can do the multiplication over and over until all the probability of $C_{start}$ transitioning to non-halting configurations are 0. Since by definition $M$ must halt within a polynomial time $T(n)$, this process must also stop within polynomial time. Note that we could calculate the numbers precisely since we only need a precision of $2^{-T(n)}$. We could use $T(n)+1$ digits to record the probabilities.

Thus, we have a TM that calculates $A$, verifies the probability of $C_{start}$ transitioning to accepting states and finally outputing 1 or 0 based on the probability. We also know this TM runs in polynomial time, so $L \in \P$, which indicates $\BPL \subseteq \P \tag*{$\blacksquare$}$.

7.10

Under Construction

7.11

Under Construction