\documentclass[fullpage]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{xspace}
\setlength{\textwidth}{5.5in}
\newcounter{prcnt}
\newenvironment{problem}{\stepcounter{prcnt}{\bf Problem \arabic{prcnt}:} }{}
%\renewcommand{\P}{\mathbf{P}}
%\newcommand{\NP}{\mathbf{NP}}
%\newcommand{\coNP}{\mathbf{coNP}}
\newcommand{\pparnp}{\P_{||}^\NP}
\newcommand{\pnplog}{\P^{\NP[\log]}}
\newcommand{\pnp}{\P^\NP}
\newcommand{\poly}{\ensuremath{\text{poly}}\xspace}
\newcommand{\defeq}{ \overset{\scriptscriptstyle{\rm def}}{=} }
\newcommand{\class}[1]{\ensuremath{\text{\bf{#1}}}\xspace}
\newcommand{\NP}{\class{NP}}
\renewcommand{\P}{\class{P}}
\newcommand{\coNP}{\class{co-NP}}
\newcommand{\US}{\class{US}}
\newcommand{\E}{\class{E}}
\newcommand{\EXP}{\class{EXP}}
\newcommand{\polyL}{\class{polyL}}
\newcommand{\DTIME}{\class{DTIME}}
\newcommand{\DSPACE}{\class{DSPACE}}
\newcommand{\Sp}[1]{\ensuremath{\class{S}^p_{#1}}\xspace}
\newcommand{\Sigp}{\mathbf{\Sigma}^p}
\newcommand{\Sigkp}[1]{\ensuremath{\Sigp_{#1}}\xspace}
%\newcommand{\problem}[1]{\ensuremath{\text{\sf #1}}\xspace}
\newcommand{\SAT}{\problem{SAT}}
\author{}
\date{}
\begin{document}
\hrule
\begin{center}
{\LARGE\sc Qualifying Examination}\\[1ex]
{\Large\sc Theoretical Computer Science}\\[1ex]
{\sc Saturday, February 28, 2009}\\[1ex]
\vspace*{0.5in}
{\Large\sc Part II: Automata and Complexity}
\end{center}
\hrule
\vfill
\begin{center}
\large
\begin{tabular}{|l||p{2in}|}
\hline
& \\
{\bf ID Number} & \\
& \\
\hline
& \\
{\bf Pseudonym} & \\
& \\
\hline
\end{tabular}
\end{center}
\vfill
{\LARGE
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
Problem & Maximum Points & Points Earned & Grader\\
\hline
\hline
1 & 25 & & \\ \hline
2 & 25 & & \\ \hline
3 & 25 & & \\ \hline
4 & 25 & & \\ \hline
Total & 100 & & \\ \hline
\end{tabular}
\end{center}
}
~ \newpage
{\bf Instructions:}
\begin{enumerate}
\item This is a closed book exam.
\item The exam is for 3 hours and has four problems of 25 points
each. Read all the problems carefully to see the order in which
you want to tackle them.
\item Write clearly and concisely. You may appeal to some standard
algorithms/facts from text books unless the problem explicitly
asks for a proof of that fact or the details of that algorithm.
\item If you cannot solve a problem, to get partial credit write
down your main idea/approach in a clear and concise way. For
example you can obtain a solution assuming a clearly stated lemma
that you believe should be true but cannot prove during the
exam. However, please do not write down a laundry list of half
baked ideas just to get partial credit.
\end{enumerate}
~\\~\\
May the force be with you.
\newpage
\noindent
\begin{problem}
Answer the following questions. Each proof should not take more
than a few steps/lines of reasoning. You can appeal to standard
results (e.g. as covered in CS 579).
\begin{enumerate}
\item Show that $\polyL \defeq \DSPACE((\log n)^{O(1)})$ does
not have any complete problems under log-space many-one
reductions.
\item Recall that $\E = \DTIME(2^{O(n)})$. Is the statement
$\P^\E = \E$ true, false or is not known? Explain.
\end{enumerate}
\end{problem}
\vspace*{0.5cm}
\noindent
\begin{problem}
A \emph{deterministic non-erasing PDA} (DNEPDA) is a deterministic
pushdown automaton such that in any execution of the machine the
height of the stack never decreases. More formally, a DNEPDA is $M
= (Q,\Sigma,\Gamma,q_0,X_0,F,\delta)$, where $Q$ is a finite set
of states, $\Sigma$ is the input alphabet, $\Gamma$ is the stack
alphabet, $q_0 \in Q$ is the initial state, $X_0 \in \Gamma$ is
the bottom stack symbol, and $F \subseteq Q$ is the set of
final/accepting states. The transition relation $\delta$ is
non-erasing in the sense that $\delta : Q \times (\Sigma\cup
\{\epsilon\}) \times \Gamma \to {\cal P}_f(Q \times \Gamma^+)$,
where ${\cal P}_f(X)$ is the collection of all finite subsets of
$X$. Thus, $(q',w) \in \delta(q,a,\gamma)$ means that $|w| > 0$
and when in state $q$ on reading $a$ with $\gamma$ on top of the
stack, the machine pops $\gamma$, pushes the symbols $w$, and
moves to state $q'$. Furthermore, $\delta$ is deterministic in
that for every $q \in Q, a \in \Sigma\cup\{\epsilon\}, \gamma \in
\Gamma$, $|\delta(q,a,\gamma)| \leq 1$, and if
$\delta(q,\epsilon,\gamma) \neq \emptyset$ then
$\delta(q,\epsilon,\gamma) = \emptyset$ for all $a$. An input $u$
is accepted by $M$ if the machine reaches a final state on $u$,
and $L(M)$ is the collection of all strings accepted by $M$. How
does the class of languages recognized by a DNEPDA compare with
regular languages and deterministic context-free languages?
(Recall that deterministic context-free languages are all
languages that can be accepted by a deterministic PDA.) Prove your
answer.
\end{problem}
\vspace*{0.6cm}
\noindent
\begin{problem}
We consider the grid-searching capabilities of various
finite-state robots walking on the infinite two-dimensional grid.
A finite state robot occupies one cell of the grid, and has a
sensor that tells it whether the cell is empty, or whether there
is a pebble in the cell. The robot has finitely many states, and
its actions include moving left, right, up, down, or diagonally,
along with putting down or picking up a pebble if so equipped.
The next state, and action (put down, pick up, move) depends only
on the current state and on whether or not there is a pebble in
the current cell and whether or not it is holding a pebble.
\begin{enumerate}
\item Describe how a robot with four pebbles can be programmed
to visit every cell in the grid (which is infinite in each of
four directions).
\item Prove that a robot with three pebbles can also visit
every cell in the grid.
\item Prove that a robot with one pebble cannot visit every
cell in the grid. (Hint: first consider the case of a robot
with no pebbles for partial credit, then extend the argument.)
\item What is the largest portion of the grid that can be
visited by robots with two pebbles?
\end{enumerate}
\end{problem}
\noindent
\begin{problem}
A language $L$ is said to be in the class \Sp2 (the second level
of the ``symmetric hierarchy'') if there is a language $F \in \P$
such that for all $x$,
\begin{align*}
x\in L \implies& \exists y, \forall z, |y|,|z|\le \poly(|x|)
\text{ and } (x,y,z) \in F \\
x\not\in L \implies& \exists z, \forall y, |y|,|z|\le
\poly(|x|) \text{ and } (x,y,z) \not\in F.
\end{align*}
In other words, for $L\in \Sp2$, there is a polynomial time
verifier which takes ``claims'' ($y$ and $z$) from two parties
such that if $x\in L$ there is a convincing claim $y$ for that,
irrespective of what $z$ says, and if $x\not\in L$ there is a
convincing claim $z$ for that irrespective of what $y$ says.
\begin{enumerate}
\item (Simple) How does \Sp2 relate to \Sigkp2? Recall that
\Sigkp2 is the class of languages for which there is a
language $F\in \P$ such that for all $x$,
\[
x\in L \iff \exists y, \forall z, |y|,|z|\le \poly(|x|) \text{
and } (x,y,z) \in F.
\]
\item Show that $\P^\NP \subseteq \Sp2$.
\end{enumerate}
\end{problem}
\end{document}