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

\newcommand{\polyL}{\mbox{PolyLog}}
\newcommand{\Poly}{\mbox{P}}
\newcommand{\NL}{\mbox{NL}}
\newcommand{\SPACE}{\mbox{SPACE}}
\newcommand{\SC}{\mbox{PolyLogSpacePolyTime}}

\head{CSG714}{Theory of Computation}{Spring 2009}{26 February 2009}{12}

\begin{center}
\Large{\bf Problem Set 4 (due Thursday, March 12)}
\end{center}

{\bf 1. (10 points) Determining whether a graph is a forest}

Show that it is possible to determine in logspace whether a given
undirected graph is a forest (i.e., has no cycles).

({\em Hint:} Note that the graph may not be connected.  Logarithmic
space means that you can only keep track of a constant number of
vertices and edges.  Start from a vertex $u$ on an edge $(u,v)$, and
explore a path, by the following simple approach: when arriving at a
node $w$, use the edge that is next on the adjacency list.  If you
loop back to $u$ along a different edge, then you have found a cycle.
Repeat this process with other vertices and edges.  Argue that this
process always detects a cycle, if and only if one exists, and
terminates while using space logarithmic in the size of the graph.)

{\bf 2. (10 points) Integer Multiplication is in L}

Problem 8.20 from Sipser's text.

{\bf 3. (10 + 10 = 20 points) Regular expressions and space complexity}

The following two parts concern the space complexity of the emptiness
or universality of regular languages given in a certain form.  

\begin{itemize}
\item[{\bf (a)}]
Show that it is $\NL$-complete to determine whether the language
generated by a given DFA is empty.

({\em Hint:} Compare with the directed reachability problem.)

\item[{\bf (b)}]
You are given a regular expression $r$ over the alphabet $\Sigma$ with
the usual operators ($\cdot$, $+$, and $^*$).  Show that it is
PSPACE-complete to determine whether the language generated by $r$ is
$\Sigma^*$.

({\em Hint:} You need to show both membership in PSPACE, and
PSPACE-hardness.  For membership in PSPACE, note that NPSPACE =
co-NPSPACE = PSPACE; take advantage of nondeterminism and the fact
that deciding the complement of the language is ``equivalent'' to
deciding the language.  For PSPACE-hardness, one could try a reduction
from a known PSPACE-hard problem such as QBF.  Easier is to give a
polynomial-time reduction from an arbitrary PSPACE language $L$: given
a PSPACE machine $M$ deciding $L$ and a string $w$, generate a regular
expression $r$ in polynomial time so that $M$ accepts $w$ if and only
if $r$ generates all strings other than the string representing the
accepting computation history of $M$ on $w$.)
\end{itemize}

{\bf 4. (10 + 2 + 8 = 20 points) $\Poly$, $\NL$, and $\polyL$}

Define the class $\polyL$ as $\bigcup_{k \ge 0} \SPACE(\log^k n)$;
i.e., the class of languages that require (deterministic)
poly-logarithmic space.

\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}

Two natural classes to consider at the ``intersection'' of $\polyL$
and $\Poly$ are (i) $\polyL \cap \Poly$ and (ii) $\SC$, the class of
languages decided by deterministic TMs that run in {\em both}\/
polylogarithmic space and polynomial time.  (Note the subtle
difference between the two definitions.)

\begin{itemize}
\item[{\bf (c)}] Show that $\NL$ is contained in $\polyL \cap \Poly$.
However, we do not know whether $\NL$ is contained in $\SC$.  Why
does this not follow from Savitch's Theorem?  In particular, what is
the running time of the algorithm for reachability in directed graphs
given in Savitch's Theorem?
\end{itemize}

{\bf 5. (10 points) Go-Moku is in PSPACE}

Problem 8.10 of Sipser's text. 

\end{document}
