\documentclass[12pt]{article}


\usepackage{geometry}
\usepackage{graphics,epsfig}
\usepackage{amsfonts}

\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}

\begin{document}

\begin{center}
\bf
CS 181d, Complexity Theory \\
Fall 2012\\
\rm
Homework 4 \\
Due Wednesday, October 3, 11:59 PM
\end{center}

\begin{enumerate}

\item \textbf{[40 Points] PSPACE $=$ NPSPACE}! 

 Before embarking on this problem, make sure that you understand the
 proof we showed in class that QBF is PSPACE-complete. 

	Recall that we defined PSPACE to be the set of all
	languages $L$ such that there exists some polynomial
	$p(n)$ and some \textbf{deterministic} TM $M$ such that on input $w$,
	$M$ uses at most the first $p(|w|)$ tape cells to determine
	whether $w$ is in $L$.

	Similarly, we can define NPSPACE to be the set of all
	languages $L$ such that there exists some polynomial
	$p(n)$ and some \textbf{nondeterministic} TM $M$ such that on 
	input $w$, if $w \in L$ then there exists some accepting
	computation path, if $w \notin L$ then there exists no
	accepting computation path, and \emph{every} computation path uses
	at most the first $p(|w|)$ tape cells.
	While it is not known whether P $=$ NP, it
	is known that PSPACE $=$ NPSPACE.  In this problem
	we'll prove this!  
	Note that NPSPACE is defined in terms of
	nondeterminism and \emph{not} defined in terms of
	verifying certificates.	

	\begin{enumerate}
		\item Professor I. Lai proposes the following
		approach:  ``Look, if $L$ is accepted by a
		nondeterministic TM $M$ in polynomial space, I will
		build a deterministic TM $M'$ that simulates $M$,
		and thus accepts the same language, and still only
		uses polynomial space!  How?  Easy!  Nondeterministic
		TM $M$ has at most $b$ nondeterministic choices at
		each step.  $M'$ will enumerate sequences in base $b$
		on a work tape and then simulate $M$ on input $w$
		using the current sequence to dictate the choices
		that $M$ would make.  If, for a given base $b$
		sequence the simulation reveals that $M$ accepts $w$,
		then $M'$ will accept $w$.  Otherwise, we will write
		down the next base $b$ sequence and try again.
		If none of these sequences work, well then, $M$ 
		can't accept $w$ so $M'$ also rejects $w$.
		In order to save space, $M'$ will overwrite the
		new base $b$ sequence over the old base $b$ sequence.
		It's so easy that I want to eat ten cans of SPAM
		to celebrate!''
		Explain why Professor Lai is celebrating a bit too
		soon.  That is, explain what's wrong with this 
		so-called proof.
		
		\item Now we will fix things to make the proof work
		correctly!  The idea is to use techniques similar to
		those employed in Stockmeyer's Theorem 
		to show that QBF is PSPACE-complete!  
		Notice that since nondeterministic TM $M$ never
		uses more than polynomial space, $p(n)$, it 
		cannot enter more than $c^{p(n)}$ different
		configurations for some constant $c$. 
		Moreover, any one of these configurations can be recorded
		in polynomial space. 

		Using this observation, argue carefully
		that a deterministic polynomial space TM $M'$ can be
		constructed to simulate TM $M$.  Make sure to show
		that no more than polynomial space is really being
		used in your simulation.  Pretty nifty!!
	\end{enumerate} 

\item \textbf{[25 Points] Generalized Lunar Lockout is in PSPACE}

In class, we described the Generalized Lunar Lockout game.  Your job is to prove that the problem is in PSPACE.  (We skipped that part in class.)
Recall that the game is played
on a $m \times m$ board.  The initial configuration is some set of objects placed on the board.  
An object may be a stationary robot (a ``rock''), a movable robot, or the special movable
target robot.  One of the cells is designated as the target cell.  The question is whether there
exists a sequence of moves that bring the special target robot to the target cell.  Notice that the
number of moves in such a ``winning'' sequence could potentially be very long! 

\item \textbf{[35 Points] Regular expressions and PSPACE.}  

Many problems related to regular expressions are known to be
in PSPACE but are not known to be in any ``lower'' complexity class.
For example, consider the problem of determining whether a given
regular expression over the alphabet $\Sigma = \{0, 1\}$ is equivalent
to $\Sigma^*$.  For example, $0^* 1^* + (0+1)1^{*}$ is not the same
same as $\Sigma^{*}$ but $1^* ((\epsilon + 1) (\epsilon +
0))^*$ is equivalent to $\Sigma^{*}$.

So, we are considering the following problem:  Given an encoding of a
regular expression, is that regular expression equivalent to $\Sigma^*$?
We'll call this problem \textsc{REGEQ} (REGular expression EQuivalence).

\begin{enumerate}
  \item First, very briefly sketch the arguments for each of the following claims (CS 81 review).  
       \begin{enumerate}
        \item Every regular expression of length $n$ has a corresponding NFA with a number of states that is linear in $n$.  (Give just a few sentences that indicate why this is so.)
        \item Every NFA with $n$ states has a corresponding DFA with at most  $2^n$ states.  (Give a two sentence explanation.)
        \item If a DFA with $k$ states accepts some string $w$ of length $k$ or more then it must also accept a shorter string.  (Very short explanation here!)
     \end{enumerate}
     
  \item  Next, consider the problem of determining whether the language of a given DFA is
$\Sigma^{*}$.  Describe a finite-time algorithm (it need not be efficient
in any sense) that takes as input a DFA and determines whether that DFA
accepts $\Sigma^{*}$.  Explain briefly why your algorithm is correct.

  \item Now, prove that \textsc{REGEQ} is in PSPACE. 
 Be careful to show that your solution works correctly and really uses
only polynomial space!  

  \item 
  Finally, consider the more general problem \textsc{REGPAIR} that takes as input
  the encodings of two regular expressions, $R_1$ and $R_2$, and determines whether or not
  these two regular expressions represent the same language.  Prove that \textsc{REGPAIR} is
  in PSPACE.  (Here, it may be useful to remind yourself that the regular languages are closed under union, intersection, and complement and remind yourself of how we prove this.)
\end{enumerate}



\end{enumerate}
\end{document}