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

\head{CSG714}{Theory of Computation}{Spring 2009}{10 February 2009}{10}

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

{\bf 1. (5 $\times$ 4 = 20 points) Complexity measures}

What is a reasonable complexity measure?  In class, we have discussed
time and space as two reasonable complexity measures, when using
Turing machines as our computational models.  In a 1967 JACM paper,
Manuel Blum considered this question and defined a {\em complexity
measure} $\Phi$ to be a function that maps Turing machine-input pairs
to nonnegative integers and is decidable.  Formally, $\Phi$ is a
complexity measure if $\Phi(M,x)$ is defined whenever $x$ is a valid
input to $M$ and it is decidable given $M$, $x$, and $k$, whether
$\Phi(M,x) = k$.  By this definition, which of these are complexity
measures?

\begin{itemize}
\item
Time, the number of steps during a computation.
\item
Space, the number of cells used on the worktape of a 2-tape Turing
machine (assuming that the first input tape is read-only).
\item
Reversals, the number of times during a computation that the head must
change direction of motion.
\item
Waste, the number of times during a computation that the head writes
the same symbol as just read by the head.
\item
Work, the number of times during a computation that the head writes a
different symbol than the one just read by the head.
\end{itemize}

{\bf 2. (10 points) Crossing sequences and regular languages} 

Show the following claim, left unproved in class.  Let $L$ be a
language and $M$ be a deterministic single-tape Turing Machine that
decides $L$.  For a given string $x$, let $c_i(x)$ denote the sequence
of states that the $M$ is in as it crosses cell $i$ to $i+1$, or vice
versa, during its computation on $x$.  And let $c(x)$ denote the
length of the longest crossing sequence among $c_i(x)$, $1 \le i \le
|x|$.  

Show that if there exists an integer $k$, such that $c(x)
\le k$ for all $x$, then $L$ is regular.

({\em Hint:} Think NFAs.)

{\bf 3. (10 points) SAT formula with no negations} 

Suppose you have a SAT formula in conjunctive normal form, in which
very literal is a nonnegated variable (e.g., $((x_1 \vee x_2 \vee x_3)
\wedge (x_1 \vee x_4) \wedge (x_2 \vee x_3 \vee x_5))$).  It is easy
to see that $\phi$ is satisfiable.  Given such a formula, a natural
goal is to select the mimimum number of variables that need to be set
true to satisfy the formula.  Show that the following language is
NP-complete.

\[
\{\langle \phi, k \rangle: \phi \mbox{ has no negated literals and is
satisfied by setting at most $k$ variables true}\}
\]

{\bf 4. (10 points) A flexible variant of Post Correspondence Problem}

Consider the following variant of the Post Correspondence Problem.  We
are given two sets of binary strings $\{t_1, \ldots, t_m\}$ and
$\{b_1, \ldots, b_n\}$.  The goal is to determine whether there exists
a string $w$ such that (a) $w$ can be written as $t_{i_1}t_{i_2}\cdots
t_{i_k}$ for some $i_1, \ldots i_k \in \{1,\ldots,m\}$ and (b) $w$ can
be written as $b_{j_1}b_{j_2}\cdots b_{j_\ell}$ for some
$j_1,\ldots,j_\ell \in \{1,\ldots,n\}$.

Show that the above problem is in NP.  Why does the same argument not
work for the Post Correspondence Problem?

{\bf 5. (10 points) Minesweeper} 

Problem 7.30 in Sipser's text.

{\bf 6. (10 points) Difference hierarchy}

Problem 7.45 in Sipser's text.
\end{document}
