\documentclass[10pt]{article} \newtheorem{define}{Definition} \usepackage{amssymb, fullpage} \newcommand{\p}{\mathop{\rm P}} \newcommand{\np}{\mathop{\rm NP}} \newcommand{\NTIME}{\mathop{\rm NTIME}} \newcommand{\TIME}{\mathop{\rm TIME}} \begin{document} \input{preamble.tex} \lecture{2}{February 12, 2007}{Madhu Sudan}{Alan Deckelbaum} \section{Administrivia} \begin{itemize} \item Make sure you're on the mailing list. You should have received an email earlier today. \item Sign up for scribing. \item Swastik's office hours: \begin{itemize} \item Thursdays 6-8pm Gates $5^{th}$ floor \item Tuesday 2/20 (same location) \end{itemize} \end{itemize} \section{Overview} The topic of lecture today is diagonalization. Specifically, we will: \begin{itemize} \item Prove $\NTIME(o(n^2)) \subsetneq \NTIME(n^{10})$. \item Prove Ladner's Theorem: $\np\ne\p$ $\Rightarrow$ $\exists L \in \np$ s.t. $L \not\in \p$ and $L \not\in$ NP-complete. \item Show the limits of Diagonalization. \end{itemize} \section{Introduction to Diagonalization} Diagonalization is the main technique we have for proving lower bounds. (However, it is very unlikely that we will be able to prove $P \neq NP$ using diagonalization, as we will see at the end of the lecture.) We start by recalling the proof idea used to show $\TIME(o(n^2)) \subsetneq \TIME(n^{10})$. (We are being sloppy with the time bound on the right hand side. If we are very careful (and clever), this time bound could be reduced to $\TIME(n^2 \log n)$.) We start by constructing a language $L$ which is not in $\TIME(o(n^2))$ but is in $\TIME(n^{10})$. We first describe the language. The idea is to {\em enumerate} all deterministic Turing Machines that run in $\TIME(n^2)$. Call these machines $$M_1, M_2, M_3, \ldots, M_j, \ldots$$ and let $L_i$ be the language accepted by $M_i$. Also, we will enumerate all binary strings $$x_1, x_2, x_3, \ldots, x_i, \ldots$$ (Notation: We will use $L(x)$ to denote the bit that is $1$ if $x \in L$ and $0$ otherwise.) We can now imagine a infinite binary matrix of with the columns indexed by the machines $M_j$, and the rows indexed by the strings $x_i$. The $(i,j)$ entry of this matrix is $L_j(x_i)$. We can now construct a language $L$ given by complementing the {\em diagonal} of this matrix, i.e., $L(x_i) = \neg(L_i(x_i))$. It is obvious by construction that $L \ne L_i$ (since $L(x_i) \ne L_i(x_i)$. What needs to be seen is that $L \in \TIME(n^{10})$. Strictly speaking this is not really true, since the $j$th machine may run in time $2^j \cdot n$. One can get around this issue by a more careful enumeration of machines, and by varying the language $L$ somewhat. We won't do so now. Instead we will simply assume each of these computations (of $L_i(x_i)$) can be {\em simulated} in $\TIME(n^10)$. This now leaves us with the task of {\em complementing} the value $L_i(x_i)$ which is easily done while staying in the class $\TIME(n^10)$. We thus see that using diagonalization to show ${\cal C}_1 \subsetneq {\cal C}_2$ relies on three basic abilities: \begin{description} \item[Enumeration:] We should be able to enumerate all machines in ${\cal C}_1$ efficiently. \item[Simulation:] We should be able to simulate the machines of ${\cal C}_1$ efficiently. \item[Complementation:] - The machine that complements the computation of the machines used in the previous two steps should be in ${\cal C}_2$. \end{description} %We would also like a way to enumerate all of the $M_i$'s. Notice that it is possible to construct a language that differs from each $M_i$ on infinitely many inputs. For example, we can use the sequence %$$M_1, M_1, M_2, M_1, M_2, M_3, \ldots$$ %This enumeration also avoids potential difficulties with constant factors on running time: $M$ will eventually differ with $M_i$ on some input that is large enough that it can be computed in the running time of our machine. Thus while the proof above works nicely for classes closed under complementation, it doesn't work when the class under consideration is not known to be closed, such as $\NTIME(o(n^2))$. In what follows, we will describe a clever variation of diagonalization, called ``lazy diagonalization'', that does not require such a strong closure with respect to complementation. \section{$NTIME(n^2) \subsetneq NTIME(n^{10})$} For now, we will focus on a single $NTIME(n^2)$ machine, $M$, of length $i$. We want to construct a language $L \neq L(M)$ (for some sufficiently long strings of length $\geq i$). Furthermore, we want to be able to prove that $L \in NTIME(n^{10})$. We notice immediately that $NTIME(n^2) \subsetneq NTIME(2^{n^3})$, as $NTIME(n^2) \subseteq TIME(2^{n^2}) \subsetneq TIME(2^{n^3}) \subseteq NTIME(2^{n^3})$. We could come up with a sequence of increasingly growing functions, say $$T_1(n), T_2(n), \dots, T_k(n)$$ where $T_1(n) = n^2$, and $T_k(n) = 2^{n^3}$. We then know that there must be some $i$ such that $$NTIME(T_i(n)) \neq NTIME(T_{i+1}(n))$$ since $NTIME(T_1(n)) \neq NTIME(T_k(n))$. Take the machine $M$, and look at all inputs between $0^i, 0^{i+1}, 0^{i+2}, \ldots, 0^I$, for some very large $I$. (The size of I will be specified in more detail later.) We will construct the language L, which shifts the above language by one 0 of the input. In other words, $0^k$ is in $L$ if and only if $0^{k+1}$ is in $L(M)$, for all $k$ between $i$ and $I-1$. We have $L \neq L(M)$ as long as it is not the case that either $0^k \in L(M)$ for all $k \in \{i,i+1,\ldots,I\}$, or instead $0^k \not\in L(M)$ for all $k \in \{i,i+1,\ldots,I\}$. Our idea to solve this potential difficulty is to \textit{deterministicially} simulate $M$ on $0^i$, and set $O^I$ to be the complement of this result. If $I$ is large enough, we will be able to deterministically simulate $M$ on $0^i$ without overstepping the time bounds. Provided that $I >> i$, we would have $$L(M) \in NTIME(T(n)) \Rightarrow L \in NTIME(T(n+1))$$ All that remains is to make $I$ large enough. This can be done by ensuring $$2^{T(i)} < T(I)$$ which can be accomplished provided that we can compute $T$ easily. In fact, this approach can be used to show that $NTIME(n^2) \neq NTIME(o(n^2))$. The complete proof combining the above approach with enumeration was not shown in lecture, but appears in the lecture notes. (The theorem was proved by Cook, and this particular proof (due to Zak) is described in Fortnow's survey on diagonalization\cite{fortnow}. See the paper by van Melkebeek and Pervyshev~\cite{beek} for more information.) \begin{theorem}[Cook\cite{cook}] For every time-constructible function $T(n)$, $$NTIME(o(T(n))) \subsetneq NTIME(T(n+1))$$ \end{theorem} This proof uses lazy diagonalization and a very effective simulation of a $NTIME(o(T(n)))$ machine. \section{Ladner's Theorem} \subsection{Background} NP-completeness was introduced in the 1970's. \begin{itemize} \item Cook 1971\cite{npcomplete} $\leftarrow$ defined NP-completeness \item Karp 1972\cite{karp} $\leftarrow$ gave many examples of NP-complete problems \item Levin 1972 $\leftarrow$ independently did work similar to that of both Cook and Karp. \end{itemize} Levin's advisor, Kolmogorov, asked Levin about graph isomorphism, factoring, and linear programming, three problems that we didn't know whether they were in $P$ and also didn't have a proof of their $NP$-completeness. (We now know that linear programming $\in P$.) We ask the question: for all $L \in NP$, is it true that either $L \in P$ or $L$ is $NP$-complete? \subsection{Ladner's Theorem} Ladner showed that if $NP \neq P$, then the answer to the above question is negative. Diagonalization is once again the tool to prove this. Assume $NP \neq P$. We want a language $L \in NP$ such that $L$ isn't $NP$-complete and $L \not\in P$. We've seen examples of proving that something isn't in $P$, but we haven't yet dealt with a situation of showing that something isn't $NP$-complete. Our proof will be based on the fact that if $L$ is $NP$-complete, then SAT can be decided by a deterministic polynomial time machine with an oracle for $L$. \\ \textbf{Notation:} $M^L$ is an algorithm $M$ using an ``oracle'' for language $L$ as a subroutine. $M^L \in P^L$ implies that $M$ runs in polynomial time, assuming it takes unit time to decide $L$. Let $$M_1, M_2, \ldots, M_i, \ldots$$ be an enumeration of polynomial time oracle machines. We would like $\rm{SAT} \neq M_1^L, M_2^L, \ldots$ (as $L$ is not $NP$-complete). Furthermore, as $L \not\in P$, we would like $L \neq M_1^\emptyset, M_2^\emptyset, \ldots$. (Recall that $\emptyset$ means an oracle for the empty language, which can clearly be simulated in polynomial time.) Our goal is to construct a language that looks like SAT some of the time and like $\emptyset$ the rest of the time. Look at the sequence $$M_1^L, M_1^\emptyset, M_2^L, M_2^\emptyset, M_3^L, M_3^\emptyset, \ldots$$ We want to construct $L$ such that $L$ is not any of these languages. On input $x$, the machine deciding $L$ will go sequentially go through the above languages to ensure that it differs from each language on some input. Specifically, on a given input, it will begin comparing the results of its own simulation on the first string in lexicographic order to the result of the first language in the above sequence on the same string. If the languages differ, the machine deciding $L$ will then proceed to test the next string against the next language in the list. If the languages do not differ, the machine will test the same language against the next string in lexicographic order. The machine additionally keeps track of how much time it has used. When the machine runs out of time, it does the following, depending on which language it is currently comparing itself against: For some $j$, $L$ may be comparing itself against $M_j^\emptyset$. If this is the case, we will set $L(x) = SAT(x)$. For some $j$, $L$ may be comparing itself against $M_j^L$. If this is the case, we will set $L(x) = 0$. All that remains is to show that $L \not\in P$. If $L \in P$, then it must be the case that for all sufficiently large inputs, $L$ is the same as $SAT$. (Otherwise, $L$ would disagree with each of the $M_j^\emptyset$ on some input and it wouldn't be in $P$.) However, if $L = SAT$ and $L = M_j^\emptyset$, then we would have $SAT \in P$, which contradicts our initial assumption that $P \neq NP$. \textbf{Exercise:} Prove that there is an undecidable problem that is not NP-hard. \section{Diagonalization and the $P$ vs. $NP$ Question} A paper by Baker, Gill, and Solovay asked whether diagonalization could be used to prove $P \neq NP$. The ``politically correct'' answer is simply that this depends on the truth of $P \neq NP$. The functional answer provided by Baker, Gill, and Soloway is based on the fact that diagonalization proofs relativize. However, the proof of $P \neq NP$ would not relativize. Enumerate $M_1, M_2, \ldots$ of oracle polynomial time machines. If each machine is given an oracle for some language $O$, we get a collection $\{M_1^O, M_2^O, \ldots \}$, the set of languages decided in $P^O$. Furthermore, we have $\{M_1^\emptyset, M_2^\emptyset, \ldots \} = P$. Similarly, by enumerating NTM's with access to oracles, we can obtain the class $NP^O$, etc. Diagonalization doesn't distinguish between the particular oracle used. Thus, if diagonalization shows $P \neq NP$, it means that $P^O \neq NP^O$ for all oracles $O$. Therefore, the following two results demonstrate that it is not likely that diagonalization can be used to show $P \neq NP$. \begin{theorem} There exists an oracle $O$ such that $P^O = NP^O$. \end{theorem} \begin{proof} Let $O$ be a PSPACE-complete language, such as TQBF. We then have $P^{TQBF} = PSPACE = NPSPACE = NP^{TQBF}$. \end{proof} \begin{theorem} There exists an oracle $O$ such that $P^O \neq NP^O$. \end{theorem} The proof uses diagonalization. A language that demonstrates this result is $$L^O = \{ x | \exists y \rm{\ such \ that\ } |y| = |x| \rm{\ and\ } O(y) = 1\}$$ We see that $L^O \in NP^O$ for all $O$. We want to choose an $O$ such that $L^O \not\in P^O$. We will ensure that $L_O \neq M_j^O$ for inputs of length greater than or equal to $i$. Look at all of the queries that $M_j$ makes to $O$ when it computes on input $x$, where $x$ of a size larger than any strings that have been declared to be in the language thus far. For all inputs of length less than $x$, $O$ answers whatever it has previously returned. The oracle also sets $O(x) = 0$. As $M_j$ can only ask polynomial many queries to $O$, for sufficiently large $i$ the polynomial in $i$ will be less than $2^i$, and thus there are other strings of length $i$ that $M_j$ has not queried. The value of these inputs can be set to negate the answer to $M_j^O(0^i)$. \begin{thebibliography}{1} \bibitem{cook} Stephen A. Cook {\em A Hierarchy for Nondeterministic Time Complexity, STOC 1972: 187-192} \bibitem{npcomplete} Stephen A. Cook {\em The Complexity of Theorem Proving Procedures, STOC 1971: 151-158} \bibitem{karp} Richard M. Karp. {\em Reducibility Among Combinatorial Problems. In Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y.. New York: Plenum, p.85-103. 1972.} \bibitem{fortnow} L. Fortnow. {\em Diagonalization. Bulletin of the European Association for Theoretical Computer Science, 71:102-112, June 2000. Computational Complexity Column.} \bibitem{beek}D. van Melkebeek and K. Pervyshev. {\em A Generic Time Hierarchy for Semantic Models With One Bit of Advice. In Proceedings of the 21st Annual IEEE Conference on Computational Complexity, pages 129-142, 2006.} \end{thebibliography} \end{document}