\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}