\documentclass[10pt]{article}
\usepackage{fullpage}
%\usepackage{psfig}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{epsfig}
\usepackage{amsmath,amscd,amssymb,amsfonts,epsf,epsfig}
\newcommand{\p}{{\rm
P}}
\newcommand{\npc}{{\rm NPcomplete}}
\newcommand{\rp}{{\rm RP}}
\newcommand{\bpp}{{\rm
BPP}}
\newcommand{\pr}{{\rm Pr}}
\newcommand{\pspace}{{\rm
PSPACE}}
\newcommand{\npspace}{{\rm NPSPACE}}
\newcommand{\np}{{\rm
NP}}
\newcommand{\conp}{{\rm
coNP}}
\newcommand{\exptime}{\hbox{EXPTIME}}
\newcommand{\MINDNF}{{\sc MinDNF}}
\newcommand{\ti}[1]{{\rm
TIME}(#1)}
\newcommand{\spc}[1]{{\rm
SPACE}(#1)}
\newcommand{\nspace}[1]{{\rm
NSPACE}(#1)}
\newcommand{\conspace}[1]{{\rm
coNSPACE}(#1)}
\newcommand{\aspace}[1]{{\rm
ASPACE}(#1)}
\newcommand{\atime}[1]{{\rm ATIME}(#1)}
\newcommand{\ap}{{\rm
AP}}
\newcommand{\al}{{\rm AL}}
\newcommand{\redp}{{<_\p}}
\newcommand{\diag}{diagonalization}
\begin{document}
\input{l2-preamble.tex}
\lecture{2}{Feb. 10, 2003}{Madhu Sudan}{Yael Tauman}
%%%% body goes in here %%%%
Today:
\begin{itemize}
\item
Savitch's theorem
\item
Diagonalization
\item
Relativization
\item
Introduction to Alternations
\end{itemize}
\section{Savitch's Theorem}
Savitch's theorem considers the relationship between
non-deterministic space and deterministic space.
\begin{theorem}[Savitch]
For all constructible functions $s(n)\geq\lg(n)$,
$NSPACE(s(n))\subseteq SPACE(O(s(n)^2))$.
\end{theorem}
The idea of the proof is first to take an NL complete language and
prove that it is in $SPACE(O(\lg^2n))$, and then to generalize
this for every constructible function $s(n)\geq\lg n$. The NL
complete language that we use is
$$PATH=\{(G,s,t,l):\exists\mbox{ path of length $\leq l$
from $s$ to $t$ in the directed graph $G$}\}.
$$
\begin{proof}
The proof is carried out by proving the following two Lemmas.
\begin{lemma}
\label{*} $PATH\in SPACE(O(\lg^2n))$.
\end{lemma}
\begin{lemma}
\label{**} Lemma \ref{*} suffice to prove Savitch's theorem.
\end{lemma}
\textbf{Proof-Sketch of Lemma \ref{*}}: Consider the following
deterministic algorithm for $PATH$. On input $(G,s,t,l)$, the
algorithm operates as follows:
\begin{enumerate}
\item
Compute $G^2$.
Recall the definition of $G^2$: The vertices in $G^2$ are the
same as in $G$ and for every pair of vertices $(u,v)$, the edge
$(u,v)$ is in $G^2$ if and only if there exists a path of length
$\leq 2$ from $u$ to $v$ in $G$.
\item
Output $PATH(G^2,s,t,\frac{l}{2})$.
\end{enumerate}
Recall the following claim, given in the previous lecture.
\begin{claim}
For any pair of languages $L_1,L_2$, if $L_1\leq L_2$ and the
reduction can be done using space $s_1$, and if $L_2\in
SPACE(s_2)$ then $L_1\in SPACE(2s_1+s_2)$.\footnote{This is a
correction to the previous lecture where it was claimed that
$L_1\in SPACE(s_1+s_2)$.}
\end{claim}
Since the first step of the algorithm uses space $O(\lg n)$, the
claim implies that the above algorithm uses space $O(\lg l\times
\lg n)=O(\lg^2 n)$.\\
\\
\textbf{Proof-Sketch of Lemma \ref{**}:} By a standard padding
argument, one can see that if $s(n)\geq\lg n$ then we can always
pad the input with enough zeros so that the algorithm using space
$s(n)$, now uses space $\lg n'$, where $n'=2^{s(n)}$ is the
length of the input after it has been padded. Then this can be
done in deterministic space $O(\lg^2 n')=O(s(n)^2)$.
\end{proof}
In complexity theory, we get a kick out of findings relation
between different complexity classes. More specifically, we would
like to find reductions such as $NL=L$, but also, we would like
to prove that certain reductions do not exist. Unfortunately, not
much is known regarding the latter. The main tool used to achieve
such impossibility results is the \emph{{\diag}} method.
\section{The Diagonalization Method}
The {\diag} technique was introduced by Cantor in the 18'th
Century. It is the most powerful tool to prove that certain
reductions do not exist. For example, the time and space
hierarchy theorems, mentioned in the previous lecture, are based
on {\diag}. Other results that use {\diag} are Rice's theorem and
Ladner's Theorem, which will be described towards the end of this
lecture. The basic idea of the {\diag} technique is the
following. Take a complexity class (a collection of languages)
${\cal C}$ and explicitly demonstrate $L\notin{\cal C}$ as
follows.
\begin{figure}[h]\label{fig:1}
\begin{center}
\epsfig{file=l2-scribe02.eps,width=4in}
\end{center}
\end{figure}
Enumerate all languages in ${\cal C}$: $L_1,L_2,L_3\ldots$ and
enumerate all strings (which correspond to integers):
$\emptyset,0,01,10,11,\ldots$ Correspond to every language $L_k$
and every string $w$ the value $1$ if $w\in L_k$ and the value
$0$ otherwise. Demonstrate that $L\notin{\cal C}$ by proving that
for every $k$, $k\in L$ iff $k\notin L_k$. That is, show that the
language $L$ corresponds to a flip of the main diagonal.
In many cases the {\diag} technique requires a special
enumeration, namely, a \emph{constructive} one. For example, let
us use the {\diag} method to prove that $TIME(n^3)\subsetneq
TIME(n)$.
\begin{enumerate}
\item
Enumerate all linear-time Turing machines: $M_1,M_2,M_3,\ldots$
\item
Define a Turing machine $M$ as follows: $\forall k$, $M(k)\neq
M_k(k)$.
\item
Show that $M$ runs in $TIME(n^3)$.
\end{enumerate}
The question to be asked is how can we enumerate all linear-time
Turning machines? One way is to enumerate \emph{all} Turing
machines rather than just the linear-time ones. However, then the
Turing machine obtained from the {\diag} method will not be in
computable in $TIME(n^3)$. We overcome this problem by enumerating
\emph{all} Turing machines: $M_1,M_2,\ldots$ and restricting
their running time to some super-linear function, such as $n\lg
n$. Thus, we get an enumeration of all Turing machines which run
in $TIME(n\lg n)$: $M_1',M_2',\ldots$ Unfortunately, this will not
necessarily give us all linear time Turing machines. The reason
is that it may be the case, for example, that for infinitely many
$k$'s, machines $M_k$ run in time $n+k$ (which is linear in $n$
but exponential in the length of $k$). By restricting their
running time to $n\lg n$, we truncate the running time of these
(linear-time) Turing machines, since the running time of $M_k(k)$
is $\lg k+k$ whereas the running time of $M_k'(k)$ is only $\lg
k\lg\lg k$.
We overcome this problem by enumerating the Turing machines in
such a way that every machine appears infinitely often. This can
be done, for example, as follows. Take any enumeration:
$M_1,M_2,\ldots$, and transform it to the following
\emph{redundant} enumeration: $M_1, M_1,M_2, M_1,M_2,M_3,\ldots$.
Now, when trying to diagonalize against $M_k$, since $M_k$
appears infinitely often, it appears also in place $\geq 2^k$.
The running time of $M_k(2^k)$ is $\lg(2^k)+k=2k$ which is
smaller than $\lg(2^k)\lg\lg(2^k)=k\lg k$, and thus its running
time will not be truncated.
It remains to note that the Turing machine $M$, defined by the
{\diag} method, is computable in $TIME(n^3)$.
\\
\\
The main question to be asked is:
$$
\mbox{\emph{Can {\diag} prove $\np\neq \p$?}}
$$
In the 70's, Baker, Gill and Solovay gave negative evidence for
this question. They introduced the notion of
\emph{relativization}, and used this notion to prove that, in
some sense, ``{\diag} cannot prove $\np\neq \p$.''
\section{Relativization}
We use the following notations
\begin{enumerate}
\item
$\p^O$ is the set of all languages accepted by deterministic
polynomial-time oracle Turing machines with oracle access to $O$.
\item
$\np^O$ is the set of all languages accepted by non-deterministic
polynomial-time oracle Turing machines with oracle access to $O$.
\end{enumerate}
Baker, Gill and Solovay noticed the following observation.\\
\\
\textbf{Observation:} If one can use the {\diag} technique to show
that $\np\nsubseteq\p$, then one can also use the {\diag}
technique to show that for every language $O$, $\np^O\nsubseteq
\p^O$.\\
\\
The idea behind this observation is the following. If we can
prove $\np\nsubseteq\p$ using {\diag}, then it means that we can
find a non-deterministic polynomial-time Turing machine $N$ that
can simulate every polynomial-time Turing machine $M$ and negate
the answer. We can augment these machines into oracle Turing
machines and obtain similar results. In other words, $N^O$ can
simulate every polynomial-time oracle Turing machine $M^O$ and
negate the answer. Thus, a similar argument shows that
$\np^O\nsubseteq\p^O$.
\begin{theorem}[BGS]\label{BGS}
There exist oracles $A$ and $B$ such that
\begin{enumerate}
\item $\p^A = \np^A$, and
\item $\p^B \neq \np^B$.
\end{enumerate}
\end{theorem}
Note that the first part of the BGS Theorem together with the
above observation imply that it is impossible to prove
$\p\neq\np$ using {\diag}. For completeness we prove both
parts of the BGS Theorem.\\
\\
\textbf{Proof-Sketch} The first part is straightforward. The idea
is to take some language that is sufficiently powerful e.g.
PSPACE-complete. Let $A$ be TQBF. Clearly $\p^A \subseteq \np^A$.
For the other direction, as TQBF is PSPACE-complete, we have
$$\np^A \subseteq \npspace = \pspace \subseteq \p^A.$$
The middle step follows from Savitch's theorem. For the second
part, the idea is that non-determinism gives us more powerful
access to the oracle, allowing us to ask exponentially more
questions than allowed by a deterministic Turing machine. For any
language $B$, let
$$L(B) = \{x|\exists w: |x|=|w| \mbox{\ and\ } B(w) = 1\}$$
One can easily observe that for every language $B$, $L(B)\in
\np^B$, because we can guess $w$ the same length as $x$, and
check if $B(w)=1$. We want to show that there exists a langauge
$B$ for which $L(B)\not \in \p^B$. This will be done by
enumerating all Turing machines $M_1,M_2,\ldots$ and showing that
there exists a language $B$ such that for every $k$, $L(B)\neq
L(M_k^B)$. The language $B$ will be defined as follows. We denote
by $M^?$ the Turing machine $M$ with oracle access to an
undetermined oracle. For every $k=1,2,\ldots$ simulate
$M_k^?(0^k)$. Reply to all oracle questions with $0$, unless a
question has already been set. In this case answer according to
the previous setting.
\begin{enumerate}
\item
If $M_k^?(0^k)=YES$ the set $B\cap\{0,1\}^k=\emptyset$.
\item
If $M_k^?(0^k)=NO$ then choose a string $y\in\{0,1\}^k$ that has
not yet been set and set $y\in B$. Intuitively, the reason that
there exists such a string $y\in\{0,1\}^k$ is that for every
$i=1,\ldots,k-1$, $M_i^?$ runs in polynomial-time and thus at
most $poly(k)$ many strings in $\{0,1\}^k$ are set.
\end{enumerate}
In both cases, $L(M_k^B)\neq L(B)$, because $M_k^B(0^n)=YES$ if
and only if $0^n\notin L(B)$.\\
\\
Note that the technique, which was used to prove that {\diag}
doesn't work, is {\diag}. One can similarly prove that there
exists an oracle $B$ such that $\np^B \neq \conp^B$.\\
The {\diag} method was also useful in other contexts. It was used,
for example, in Rice's Theorem and Ladner's Theorem.
\begin{theorem}[Rice]
If $\np\neq\p$ then determining whether $L\in\np$ is also in $\p$
is undecidable.
\end{theorem}
\begin{theorem}[Ladner, 1973]
If $\p \not = \np$, then for all $k\ge 1$, there are languages
$L_1, \ldots, L_k \in \np$ such that
$$L \redp L_1 \redp \cdots \redp L_k \redp L'$$
where L $\in \p$ and $L'$ is $\npc$.
\end{theorem}
\section{Introduction to Alterations}
Relativization, which was used in the BGS Theorem, turned out to
be a very interesting concept. Consider the following question:
why do we use $TQBF$ (a \pspace-complete) problem for the first
part of BGS Theorem? Isn't an NP-complete problem sufficiently
powerful? That is, isn't $\np^{SAT}=\p^{SAT}=\np$? To answer this
question, we should answer if $\np^{\np} = \np$? Note that if
$\np=\np^{\np}$ then it follows that $\np=co\np$. The reason is
that $co\np\subseteq\np^{\np}$. Thus, we tend to believe that
$\np\neq\np^{\np}$. Consider for example the following language:
$$
\mbox{\MINDNF\ }=\{(\phi, k):\mbox{ where $\phi$ is a DNF formula
and }\exists\mbox{ DNF formula $\psi$ s.t. $|\psi| \le k$ and
$\psi$ is equivalent to $\phi$}\}.
$$
This language captures what can be done in $\np^{\np}$.
\begin{proposition}
\MINDNF\ is in $ \np^{\np}$.
\end{proposition}
\begin{proof}
We can construct a non-deterministic oracle Turing machine, which
uses a SAT oracle, to solve \MINDNF.
\begin{enumerate}
\item First guess $\psi$ of length $\le k$.
\item Ask SAT oracle if there exists an assignment $x$ such that $\psi(x) \not
=\phi(x)$.
\item Accept if oracle says No, otherwise reject.
\end{enumerate}
\end{proof}
This motivated Meyer and Stockmeyer to define a hierarchy of
complexity classes starting with
$$\Sigma^P_2=\np^{\np}.$$
We will elaborate on this hierarchy in the next lecture.
\end{document}