chapter10.tex

\section{Chapter 10}

\begin{enumerate}

%		10.19		%
\item[10.19]Show that if $\NP \subseteq \BPP$, then $\NP = \RP$. 

\par \textbf{Solution:} Since $\RP \subseteq \NP$, we only need to show $\NP \subseteq \RP$. So assume $\NP \subseteq \BPP$. Therefore, $\SAT \in \BPP$, and since it is $\NP$-complete, we only need to show it is in $\RP$.

\par Let $M$ be a probabilistic poly-time TM that accepts $\SAT$ with error at most $\frac{1}{3}$. 

\end{enumerate}