\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\newcommand{\PCP}[3]{\mbox{PCP}_{#1}(#2,#3)}
\newcommand{\SUBSTRING}{\mbox{\sc Substring}}
\newcommand{\QBF}{\mbox{\sc QBF}}
\newcommand{\NL}{\mbox{NL}}
\newcommand{\NP}{\mbox{NP}}
\newcommand{\IP}{\mbox{IP}}
\newcommand{\PSPACE}{\mbox{PSPACE}}

\head{CSG714}{Theory of Computation}{Spring 2008}{8 April 2008}{20}

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

{\bf 1. (5 + 5 = 10 points) Amplification of soundness error for PCPs}

Define $\PCP{\eps}{r(n)}{q(n)}$ as the set of languages that have a
PCP protocol using $O(r(n))$ random bits and $O(q(n))$ queries to
achieve soundness error $\eps$ (there is no error with respect to
completeness).  Thus, $\PCP{}{r(n)}{q(n)}$ is $\PCP{1/2}{r(n)}{q(n)}$.
\begin{itemize}
\item[{\bf (a)}] Suppose $L$ is in $\PCP{1/2}{r(n)}{q(n)}$.  Prove
that for any $k > 0$, $L$ is in $\PCP{1/2^k}{kr(n)}{kq(n)}$.

\item[{\bf (b)}] Using the PCP Theorem, show that $\NP$ is a superset
of $\PCP{1/n}{\log n}{\log n}$.
\end{itemize}

{\bf 2. (7 points) ZPP} 

Problem 10.20 from Sipser's text.

{\bf 3. (7 points) BPL}

Problem 10.22 from Sipser's text.

{\bf 4. (6 $\times$ 6 = 36 points) A random walk through CSG714} 
\begin{itemize}
\item[{\bf (a)}] Let $A$ be any regular language over the alphabet
$\Sigma$. Define
\[
     \SUBSTRING(A) = \{x ~|~ \exists w, y : wxy \in A \}
\]

Prove or disprove: $\SUBSTRING(A)$ is a regular language.

\item[{\bf (b)}]
Let $L$ be the language 

\[
\{\langle M \rangle ~|~ M \mbox{ is a DFA and accepts all
palindromes}\}
\]

Prove or disprove: $L$ is decidable.

\item[{\bf (c)}]
In our proof of the existence of a language that is not
Turing-recognizable, we showed that the set of all Turing machines
over a fixed input alphabet $\Sigma$ is countable, while the set of
all languages over $\Sigma$ is uncountable.  In practice, of course,
the input alphabets of different Turing machines could be different.
Suppose we have an infinite countable set $S$ of symbols $\{a_1, a_2,
\ldots, \}$ from which the alphabet for every Turing Machine is
chosen.  Is it still true that the set of all Turing machines is
countable?  (Note that even though the set $S$ is infinite, the
alphabet for each Turing machine is finite.)

\item[{\bf (d)}]
Are all context-free languages in $\NL$?

\item[{\bf (e)}]
Consider the following argument.  $\QBF$ is complete for $\PSPACE$
with respect to logspace reductions.  $\QBF$ is in linear space.
Thus, every problem in $\PSPACE$ can be reduced to a linear space
problem using logspace reductions.  So $\PSPACE$ is, in fact, equal to
linear space.

Is there a fallacy in the above argument?

\item[{\bf (f)}]
In our definition of the Interactive Proofs class (\IP), we assumed
two-sided errors (say, $1/3$ error in both soundness and
completeness).  Define $\IP^*$ as the class of languages that have IP
protocols with soundness error at most $1/3$ and no completeness
error.  Is $\IP^*$ identical to $\IP$?
\end{itemize}
\end{document}
