\documentclass{article}
\input{6045preamble}


\begin{document}
\handout{18}{Prof. Ron Rivest}{9 May 2002}{Jonathan
  Herzog}{Handout 18: Recitation Problems}

\begin{enumerate}
\item Suppose $L$ is a language and $M$ is a probabilistic
  polynomial-time decider such that
  \begin{itemize}
  \item $Pr\left[ M(x) \mbox{ accepts } \vert x \in L \right] \geq .9$,
    and 
   \item $Pr\left[ M(x) \mbox{ accepts } \vert x \not \in L \right] \leq .1$
  \end{itemize}
Is $L \in \BPP$?

\item Suppose $L$ is a language and $M$ is a probabilistic
  polynomial-time decider such that
  \begin{itemize}
  \item $Pr\left[ M(x) \mbox{ accepts } \vert x \in L \right] \geq .6$,
    and 
   \item $Pr\left[ M(x) \mbox{ accepts } \vert x \not \in L \right] \leq .4$
  \end{itemize}
Is $L \in \BPP$?

\item Suppose $L$ is a language and $M$ is a probabilistic
  polynomial-time decider such that
  \begin{itemize}
  \item $Pr\left[ M(x) \mbox{ accepts } \vert x \in L \right] \geq .9$,
    and 
   \item $Pr\left[ M(x) \mbox{ accepts } \vert x \not \in L \right] \leq .8$
  \end{itemize}
Is $L \in \BPP$?

\item Suppose $L$ is a language and $M$ is a probabilistic
  polynomial-time decider such that
  \begin{itemize}
  \item $Pr\left[ M(x) \mbox{ accepts } \vert x \in L \right] \geq .1$,
    and 
   \item $Pr\left[ M(x) \mbox{ accepts } \vert x \not \in L \right] =0$.
  \end{itemize}
Is $L \in \BPP$? Is $L \in \NP$?


\item Suppose $L$ is a language and $M$ is a probabilistic
  polynomial-time decider such that
  \begin{itemize}
  \item $Pr\left[ M(x) \mbox{ accepts } \vert x \in L \right] =
    \frac{1}{2^{\length{x}}}$, and
   \item $Pr\left[ M(x) \mbox{ accepts } \vert x \not \in L \right] =0$.
  \end{itemize}
Is $L \in \BPP$? Is $L \in \NP$?


\item Suppose $L$ is a language and $M$ is a probabilistic
  polynomial-time decider such that
  \begin{itemize}
  \item $Pr\left[ M(x) \mbox{ accepts } \vert x \in L \right] = 1 -
    \frac{1}{2^{\length{x}}}$,
    and 
   \item $Pr\left[ M(x) \mbox{ accepts } \vert x \not \in L \right] =\frac{1}{2^{\length{x}}}$.
  \end{itemize}
Is $L \in \BPP$? Is $L \in \NP$?



\item Suppose you have a source of unbiased bits. Show how to pick a
  random element from $\set{1,\ldots n}$ with uniform probability. How
  many bits do you expect to use? 
  
\item Suppose you have a source of unbiased bits. Show how to pick a
  random element from $\set{2, 3,\ldots 12}$ with the same probability
  as that of rolling two dice. How many bits do you expect to use? 
  
\item Suppose you have a source of unbiased bits. Show how to pick a
  random permutation on $\set{1, 2,\ldots n}$ with uniform
  probability. How many bits do you expect to use? 

\end{enumerate}
\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
