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

\newcommand{\halfnfa}{\mbox{{\sc Half-Paths-NFA}}}

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

\begin{center}
\Large{\bf Problems of the Week -- 7 \& 8}
\end{center}

{\noindent {\bf NL-Completeness}}

Prove the following problem is NL-complete.  

Given a regular expression $r$, is the language of $r$ empty?

\medskip

{\noindent {\bf PSPACE-Completeness}}

Prove that the following problem is PSPACE-complete.

Given a Turing Machine $M$ and input $w$, determine whether $M$
accepts $w$ without ever moving its head beyond the first $|w|$
symbols of the tape.

\end{document}


