\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newcommand{\SPACE}{\mbox{{\sc SPACE}}}
\newcommand{\NSPACE}{\mbox{{\sc NSPACE}}}
\newcommand{\NP}{\mbox{{\sc NP}}}
\newcommand{\RP}{\mbox{{\sc RP}}}
\newcommand{\BPP}{\mbox{{\sc BPP}}}
\newcommand{\IP}{\mbox{{\sc IP}}}
\newcommand{\Poly}{\mbox{{\sc P}}}
\newcommand{\polyL}{\mbox{{\sc PolyLog}}}
\newcommand{\SAT}{\mbox{{\sc SAT}}}
\newcommand{\CSAT}{\mbox{{\sc CIRCUIT-SAT}}}
\newcommand{\CVP}{\mbox{{\sc CVP}}}
\newcommand{\SVP}{\mbox{{\sc SVP}}}
\newcommand{\CNFSVP}{\mbox{{\sc CNFSVP}}}
\head{CSG714}{Theory of Computation}{Spring 2008}{25 March 2008}{17}

\begin{center}
\Large{\bf Problem Set 5 (due Friday, April 4)}
\end{center}

{\bf 1. (10 + 10 = 20 points) Use of the padding technique in separation results}

Problems 9.13 and 9.14 in Sipser's text.

{\bf 2. (10 points) Alternating machines} 

Assume $S(n) \ge log(n)$ and is space-constructible.  Prove that
\[
\bigcup_{k > 0} \left(\Sigma_k \SPACE(S(n)) \cup \Pi_k \SPACE(S(n))
\right) = \NSPACE(S(n)).
\]

That is, prove that any language decidable by alternating Turing
machines with a fixed number of alternations in space $S(n)$ is also
decidable by a nondeterministic Turing machine in space $S(n)$.

{\bf 3. (10 points) The class $\polyL$} 

Define the class $\polyL$ as $\bigcup_{k \ge 0} \SPACE(\log^k n)$.  

\begin{itemize}
\item[{\bf (a)}] Prove that $\polyL$ does not have any language that
is complete with respect to logspace reductions.  That is, show that
there does not exist any language $A \in \polyL$ such that every
language $B$ in $\polyL$ reduces to $A$ in logarithmic space.

\item[{\bf (b)}] Using (a), argue that $\polyL \neq \Poly$.
\end{itemize}

{\bf 4. (10 points) Classes \NP, \BPP, and \RP}

Problem 10.19 in Sipser's text: Show that if $\NP \subseteq BPP$, then
$\NP = \RP$.

{\bf 5. (10 points) Amplification lemma for $\IP$} 

Fix any real $\eps > 0$.  Show that if a language $A$ is in $\IP$ then
there exists a prover $P$ and a polynomial-time verifier $V$ such
that:
\begin{itemize}
\item 
$w \in A$ implies that $\Pr[V \leftrightarrow P \mbox{ accepts } w] \ge 1-
\eps$.

\item 
for any prover $\widetilde P$, $w \notin A$ implies that $\Pr[V
\leftrightarrow \widetilde P \mbox{ accepts } w] \le \eps$.
\end{itemize}

How small can $\eps$ be made, as a function of $|w|$?

\end{document}
