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

\head{CSG714}{Theory of Computation}{Spring 2008}{13 February 2008}{9}

\begin{center}
\Large{\bf Problem Set 3 (due Friday, February 22)}
\end{center}

{\bf 1. (5 + 5 = 10 points) Window size in the proof of Cook-Levin
Theorem}

In the proof of Cook-Levin Theorem, we captured the legal moves of a
Turing machine by considering a 2-row 3-column window of the grid
containing the computation history of a Turing machine running on a
particular input.  Show why the proof would have failed if we had used

\begin{itemize}
\item[{\bf (a)}]
$2$-row $2$-column windows;

\item[{\bf (b)}]
two entire rows as our window (i.e., a $2$-row, $n^k+3$-column
window).
\end{itemize}

{\bf 2. (15 points) Generic complete problems}

Show that all languages in $\mbox{TIME}(T(n))$ reduce to the language

\[
\{\langle M, x \rangle: M \mbox{ is a deterministic TM that accepts } x
{ in } T(|x|) \mbox{ time} \}.
\]

Is the above language in $\mbox{TIME}(T(n))$?  

Repeat the above exercise for nondeterministic time classes.

{\bf 3.  (15 points) PUZZLE is NP-complete} 

Problem 7.26 from Sipser's text.

{\bf 4. (10 + 10 = 20 points) 0-1 Linear equations} \hs 

Let $A$ be an $m \times n$ matrix over the integers and $\hbox{\bf b}$
be a vector of length $m$ over the integers.  Define {\em LINSOL} to
be the language $\langle A,
\hbox{\bf b}\rangle$ such that there exists a length-$n$ vector
$\hbox{\bf x}$ with components 0s or 1s that satisfies $A\hbox{\bf x}
= \hbox{\bf
  b}$.
\begin{itemize}
\item[{\bf (a)}] 

Prove that {\em LINSOL} is NP-complete.

\bigskip

\item[{\bf (b)}] Consider the sublanguage of {\em LINSOL} with $A$
restricted to all zeros except for at most two 1s in each row and
$\hbox{\bf b}$ restricted to all 1s.  Show that there is a polynomial
algorithm to recognise this language.

{\em Hint:} Note that if $x$ and $y$ are restricted to be in $\{0,
1\}$, then $x + y = 1$ if and only if exactly one of $x$ and $y$ is
$1$.
\end{itemize}

{\bf 5. (10 points) Space complexity}

Prove that if $\mbox{NSPACE}(n) = \mbox{DSPACE}(n)$, then
$\mbox{NSPACE}(S(n)) = \mbox{DSPACE}(S(n))$ for all $S(n) \ge n$.

\end{document}