\documentclass{article}
\usepackage{fullpage}
\usepackage{amssymb}
\usepackage{graphicx}
\setlength{\parskip}{.4cm}
\setlength{\baselineskip}{15pt}
\setlength{\parindent}{0cm}
\newcounter{probcnt}
\newenvironment{problem}{\stepcounter{probcnt}{\bf Problem \arabic{probcnt}}.}{}
\newcommand{\np} {{\rm NP}}
\newcommand{\p} {{\rm P}}
\newcommand{\pspace} {{\rm PSPACE}}
\newcommand{\pf} {{\rm PF}}
\newcommand{\pspacef} {{\rm PSPACEF}}
\newcommand{\E} {{\rm E}}
\newcommand{\NE} {{\rm NE}}
\newcommand{\DTIME} {{\rm DTIME}}
\newcommand{\NTIME} {{\rm NTIME}}
\newcommand{\coNP} {{\rm co-NP}}
\author{}
\date{}
\begin{document}
\hrule
\begin{center}
{\LARGE \sc Qualifying Examination} \\[1ex]
{\Large \sc Theoretical Computer Science}\\[1ex]
{\sc Friday, February 15, 2008}\\[1ex]
\vspace*{0.5in}
{\Large \sc Part II: Formal Languages and Complexity Theory}
\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 & 50 & & \\ \hline
2 & 50 & & \\ \hline
3 & 50 & & \\ \hline
4 & 50 & & \\ \hline
Total & 200 & & \\ \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 50 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
\renewcommand{\labelenumi}{(\Alph{enumi})}
\begin{problem}
Recall that a probability distribution over a (finite) set $X$ is $\mu
: X \to [0,1]$ such that $\sum _{x \in X} \mu(x) = 1$; the collection
of all probability distributions over $X$ will be denoted by ${\rm
Distr}(X)$. A \emph{probabilistic finite automaton (PFA)} is a
finite automaton that on reading an input symbol tosses a coin to
decide the next state. Formally, a PFA over alphabet $\Sigma$ is a
tuple $M = (Q, q_0, \delta, F)$, where $Q$ is finite set of states,
$q_0 \in Q$ is the initial state, $F \subseteq Q$ is a set of final
states, and $\delta: Q \times \Sigma \to {\rm Distr}(Q)$ is the
transition function.
On an input $w = a_1a_2\cdots a_n$, the probability of a run $\rho =
q_0,q_1,\ldots q_n$ is given by
\[
Pr_w(\rho) = \Pi_{i = 1}^n \delta(q_{i-1},a_i)(q_i)
\]
We will say $\rho = q_0,q_1,\ldots q_n$ is an \emph{accepting run} if
$q_n \in F$. The probability of accepting $w$, denoted by $Pr(w)$, is
the probability of all accepting runs, i.e.,
\[
Pr(w) = \sum_{\rho \mbox{ accepting}} Pr_w(\rho)
\]
Finally, for a fixed $\lambda$, $L_\lambda(M) = \{w\: |\: Pr(w) >
\lambda\}$; in other words, $L_\lambda(M)$ is the set of all words
accepted by $M$ with probability $> \lambda$.
Consider a PFA $M$ with the property that for every $w \in \Sigma^*$,
$|Pr(w) - \lambda| > \epsilon$; in other words, a string $w$ is either
accepted with probability $< \lambda - \epsilon$ or with probability
$> \lambda + \epsilon$. Prove that for such an $M$, $L_\lambda(M)$ is
regular. \emph{Hint:} Use the Myhill-Nerode Theorem.
\end{problem}
\begin{problem}
Let $M^A$ denote an oracle TM $M$ with oracle $A$. We will say $A$ is
\emph{polynomial time Turing reducible} to $B$ (denoted as $A \leq_T
B$) if there is a deterministic polynomial time machine $M$ such that
$A = L(M^B)$. A complexity class ${\cal C}$ is said to be
\emph{closed} under $\leq_T$ if whenever $A \leq_T B$ and $B \in {\cal
C}$ then $A \in {\cal C}$.
\begin{enumerate}
\item {\bf [25 points]} Show that $\np$ is closed under $\leq_T$ iff
$NP$ is closed under complementation.
\item {\bf [25 points]} An oracle machine $M$ is said to be
\emph{positive} iff whenever $A \subseteq B$ then $L(M^A) \subseteq
L(M^B)$. We will say $A$ is \emph{polynomial time positive Turing
reducible} to $B$ (denoted as $A \leq_T^{{\rm pos}} B$) if there
is deterministic polynomial time positive oracle machine $M$ such
that $A = L(M^B)$. Prove that $\np$ is closed under $\leq_T^{{\rm
pos}}$, where closure under $\leq_T^{{\rm pos}}$ is defined in
the same way as closure under $\leq_T$.
\end{enumerate}
\end{problem}
\begin{problem}
A Turing Machine computing a (partial) function is a machine with a
read-only input tape, finitely many read-write work tapes, and a
write-only output tape. The value of the function on an input $w$ is
the string written on the output tape when the machine halts on input
$w$; if the machine does not halt then the function is assumed to be
not defined on $w$. The space used by such a machine is all the tape
cells (including those on the output tape) that are either read from
or written to during the computation. The time taken by the machine is
the number of steps it takes on the input. Define $\pf$ to be the
class of all (partial) functions computable in polynomial time, and
$\pspacef$ to be the class of all (partial) functions computable in
polynomial space.
\begin{enumerate}
\item {\bf [15 points]} Prove that if $\pf = \pspacef$ then $\p
= \pspace$.
\item {\bf [35 points]} Prove that if $\p = \pspace$ then $\pf =
\pspacef$.
\end{enumerate}
\end{problem}
\begin{problem}
Given a graph $G=(V,E)$ and two nodes $s,t$ the $s,t$ longest path
problem is to find a {\em simple} path from $s$ to $t$ of the longest
possible length. Suppose a famous researcher has shown that unless
$P=NP$ the $s,t$ longest path problem does not admit a
$2$-approximation. Use this to show that unless $P=NP$ the $s,t$
longest path problem does not admit an $\alpha$-approximation for any
fixed constant $\alpha$.
\end{problem}
$\underline{\mbox{Additional Problems}}$
\begin{problem}
Prove or disprove:
\begin{enumerate}
\item $\p = \p/\log$.
\item $\np \subseteq \p/\log \Rightarrow \p = \np$.
\end{enumerate}
\end{problem}
\begin{problem}
Recall the classes $\E=\DTIME(2^{O(n)})$ and $\NE=\NTIME(2^{O(n)})$.
Show that the following are equivalent:
\begin{enumerate}
\item A language is {\em unary} if it is a subset of $\{1\}^*$ ---
that is, it only uses one symbol of the alphabet. Every unary
language in $\np$ is also in $\p$.
\item $ \E = \NE $.
\end{enumerate}
\end{problem}
\begin{problem}
A student just learned about the classes $\np$ and $\coNP$, and has
come back with the following results and proofs. In each result/proof,
find any errors. If the result is correct but the proof is wrong, give
a corrected proof.
\begin{enumerate}
\item Let $L_1, L_2$ be languages in $\np$. Then the following languages
are also in $\np$:
\begin{itemize}
\item $L_1 \cup L_2 = \{ x | x\in L_1 \mbox{ or } x\in L_2 \}$.
\item $L_1 \cap L_2 = \{ x | x\in L_1 \mbox{ and } x\in L_2 \}$.
\item $L_1 \oplus L_2 = \{ x | x \mbox{ belongs to exactly one of } L_1, L_2 \}$.
\end{itemize}
\noindent{\bf Proof:} We will prove $L_1 \cup L_2 \in
\np$. (The other proofs are similar.) Since $L_1\in\np$ and
$L_2\in\np$ there are two polynomial time non-deterministic
Turing Machines $M_1$ and $M_2$ that decide $L_1$ and
$L_2$. We build an NTM $M_3$ for $L_1 \cup L_2$ as follows:
$M_3$ on input $x$ simulates $M_1(x)$ and then $M_2(x)$ and
accepts $x$ if either of them accepts. Note that $M_1$ and
$M_2$ will make non-deterministic moves, but $M_3$ can
simulate them because it is also non-deterministic. Further,
$M_3$ takes only polynomial time because $M_1$ and $M_2$ are
polynomial time NTMs. Finally, clearly the inputs accepted by
$M_3$ are exactly $x\in L_1 \cup L_2$.
For $L_1\cap L_2$, we will have $M_3$ accept only if both
$M_1$ and $M_2$ accept, and for $L_1\oplus L_2$, we will have
$M_3$ accept if exactly one of $M_1$ and $M_2$ accepts.
\item $\np=\coNP$.\\
\noindent{\bf Proof:} This follows from the last item
above. Given any language $L\in\np$, we will show that
$L\in\coNP$. (This shows $\np\subseteq\coNP$, which in turn is
easily seen to imply $\np=\coNP$.) Define $U$ to be the
language of all strings: i.e., $U=\Sigma^*$, if $\Sigma$ is
the alphabet. Clearly $U\in\np$. By the last item above, we
have $L\oplus U \in \np$. But $L\oplus U = \overline{L}$, the
complement of $L$. Thus $\overline{L}\in\np$ or equivalently
$L\in\coNP$, as required.
\end{enumerate}
\end{problem}
\end{document}