\documentclass[11pt]{article} \textwidth=6in \oddsidemargin=0.25in \evensidemargin=0.25in \topmargin=-0.1in \footskip=0.8in \parindent=0.0cm \parskip=0.3cm \textheight=8.00in \setcounter{tocdepth} {3} \setcounter{secnumdepth} {2} \sloppy \newtheorem{example}{Example} % \P and \time are already used by LaTeX. :-( \newcommand{\ti}{\hbox{TIME}} \newcommand{\spa}{\hbox{SPACE}} \newcommand{\p}{\hbox{P}} \newcommand{\np}{\hbox{NP}} \newcommand{\pspace}{\hbox{PSPACE}} \newcommand{\lspace}{\hbox{L}} \newcommand{\conp}{\hbox{coNP}} \newcommand{\exptime}{\hbox{EXPTIME}} \newcommand{\elem}{\hbox{E}} \newcommand{\ntime}{\hbox{NTIME}} \begin{document} \input{preamble.tex} \lecture{1}{February 3, 1998}{Daniel A. Spielman}{Zulfikar A. Ramzan} \section{Course Overview} In 18.404/6.840, the prerequisite for this course, Mike Sipser discussed the issue of \p\ vs. \np . In this course, we hope to understand \p , \np\ and much much more. We will discuss topics such as: Randomness and Computation, Counting Classes, the Polynomial Hierarchy, Circuit Complexity, Interactive Proofs, etc. There will be 4-5 problem sets. If you can get at least 60\% of the problems correct, you will get an A. You are allowed to collaborate and use other sources, as long as you cite any help you received. \section{Time Complexity Classes} Define \begin{eqnarray*} \ti(t(n)) = \{\hbox{languages } L : L \hbox{ is accepted by a Turing machine that halts}\\ \hbox{within } O(t(n)) \hbox{ steps}\}. \end{eqnarray*} % I couldn't get it to break the displayed equation without doing % this. We won't specify the sort of Turing machine (e.g., one or two tape, or even a RAM or Kolmogorov machine). As long as we are consistent, it won't matter. Different definitions can change times by a polynomial factor, but that does not change the definitions of classes like $\p$ and $\np$. Also note that we used big $O$ notation in our definition. We won't look at constant factors in too much detail for this course. Blum proved results a while back formally showing that we can more or less ignore constant factors for the time complexity classes in which we are interested. Define $$ \p = \bigcup_{k \ge 0} \ti(n^k). $$ Of course, the ``P'' stands for ``polynomial time''. We'll treat $\p$ as the class of languages that can be computed reasonably/efficiently. Define $$ \exptime = \bigcup_{k \ge 0} \ti(2^{n^k}). $$ Another interesting class is: $$ \elem = \bigcup_{k \ge 0} \ti(k^n). $$ Obviously $\p \subset \exptime$. One of the few facts we'll prove in this course is that $\p \ne \exptime$. Most of the other statements we deal with will depend on unproved hypotheses. For example, we might prove that $\p \ne \np$ implies that a certain problem is hard, but we generally won't be able to prove it unconditionally. We can in fact prove the following theorem, which is much stronger than $\p \ne \exptime$. \begin{theorem}[Time Hierarchy Theorem] If $f(n) = o(g(n)/\log g(n))$, and $f$, $g$ are ``well behaved'' then $$ \ti(f(n)) \ne \ti(g(n)). $$ \end{theorem} This theorem was proved in a prerequisite class. The proof is an application of diagonalization. Also, we won't go into exactly what it means for a function to be ``well behaved.'' We more or less mean that the functions are efficiently computable by a Turing Machine. Most of the functions we will deal with in this course exhibit this property. % The proof wasn't given in detail in class. Should I insert more % details? Define \begin{eqnarray*} \ntime(t(n)) = \{L : L \hbox{ is accepted by a non-deterministic Turing machine}\\ \hbox{that always halts within } O(t(n)) \hbox{ steps}\}. \end{eqnarray*} Recall that a non-deterministic Turing machine has non-deterministic states, where it can branch. The machine accepts if at least one of its non-deterministic branches leads to an accepting computation. Non-deterministic polynomial time is defined as: $$ \np = \bigcup_{k \ge 0} \ntime(n^k). $$ The fundamental question we'd like to answer is whether $\p = \np$. Unfortunately, we've got no idea how to answer it. Most people believe, however, that $\p \neq \np$ One useful way to think of languages in $\np$ is as follows. A language $L$ is in $\np$ if and only if one can verify membership efficiently via short witnesses. More formally, that means that there is a language $L' \in \p$ and a polynomial $p(n)$ such that $x \in L$ iff there exists $w$ such that $(x,w) \in L'$ and $|w| \le p(|x|)$. Such a string $w$ is called a witness. \section{Space Complexity Classes} Define \begin{eqnarray*} \spa(t(n)) = \{L : L \hbox{ is accepted by a non-deterministic Turing machine}\\ \hbox{that uses at most } O(t(n)) \hbox{ space on inputs of length } n\}. \end{eqnarray*} Define $$ \pspace = \bigcup_{k \ge 0} \ti(n^k). $$ These are the set of languages that can be accepted in a polynomial amount of space. In other words you can design a Turing Machine that decides the language, but which only uses polynomially many (in the input size) tape cells. It's obvious that $\p \subset \pspace$, but we don't know whether $\p = \pspace$. Many people conjecture that these two classes are indeed different. In fact, if it were the case that $\p = \pspace$ then most of what we learn in this course would become irrelevant! Moreoever, we don't even know whether $\np = \exptime$ or whether $\np = \pspace$! Another interesting complexity class we examine in this course is: $$ \lspace = \spa(\log n) $$ For this particular complexity class, we assume we are dealing with a variant of a turing machine in which there is a read-only input tape, and a seperate work tape. It turns out that $\lspace \neq \pspace$. In fact, the following theorem gives us a much stronger result: \begin{theorem}[Space Hierarchy Theorem] If $f(n) = o(g(n))$, and $f$, $g$ are ``well behaved'' then $$ \spa(f(n)) \ne \spa(g(n)). $$ \end{theorem} The proof of this theorem uses the same techniques as in the proof of the Time Hierachy Theorem. It was also covered in the prerequisite course. One corollary of this theorem is that either $\lspace \ne \p$ or $\p \ne \pspace$, but we don't know which of these facts is true! \section{Reductions, Completeness, and Hardness} Perhaps the most intuitive kind of reductions are the {\sl Polynomial Time Turing Reductions}. These reductions are sometimes refered to as {\sl Cook Reductions} in the literature. A language $A$ is {\sl polynomial-time Turing reducible} to $B$ if there is a polynomial-time oracle Turing machine $M^?$ that accepts $A$ while using $B$ as an oracle. We write $A \le_T B$ in this case. What this definition means is that the Turing machine has access to a ``magic'' oracle that will answer questions of the form ``is $x \in B$'' in one step. More precisely, an {\sl oracle Turing machine} has a special tape on which it can write queries, which are then answered in one step. (We call it an oracle because the oracle is allowed to give answers that could not have been computed efficiently, or even at all.) The reason for using the ? symbol in the notation is that the Oracle Turing Machine itself can be defined independently of the actual oracle you plug in to the machine. Another type of reduction is the {\sl Polynomial-Time Karp Reduction}. There are many different names for this type of reduction: many-to-one reductions, mapping reductions, or even polynomial time reductions. A language $A$ is {\sl Karp reducible} to a language $B$ if there is a polynomial-time computable function $f$ such that $x \in A$ iff $f(x) \in B$. We write $A \le_m B$ in that case. The idea is that this condition implies that testing membership in $A$ is no harder than testing membership in $B$. A language is said to be {\sl NP-hard} if for all $A \in \np$, $A \le_m L$. A language $L$ is called {\sl $\np$-complete} if: \begin{enumerate} \item $L \in \np$ \item $L$ is NP-hard. \end{enumerate} If any $\np$-complete problem is in $\p$, then $\p = \np$. Examples of $\np$-complete languages include circuit satisfiability (given a Boolean circuit with one output, can it be made $1$?), SAT, and 3SAT. We defined the notions of hardness and completeness with specific reference to Karp reductions. We can define these notions under other kinds of reductions -- in some cases we'll need to in order for the defintions to make sense. Define $$ \conp = \{L : \bar{L} \in \np\}. $$ Here $\bar{L}$ is the complement of $L$. We do not know whether $\np=\conp$, but most people conjecture that these two complexity classes are inequivalent. We can define the notion of {\sl co-NP completeness} analagously. {\sl Tautology} (the language consisting of boolean formulae that are true on under all assignments) is the standard example of a co-NP complete problem. Notice that the Turing reduction gives a perfectly good notion of hardness (in the sense that $\p=\np$ if any $\np$-hard language is in $\p$), but it is not the same notion one gets from mapping reduction. For example, every $\conp$-complete language is $\np$-hard under Turing reductions. In particular, $co-SAT \leq_T SAT$ since a $SAT$ oracle can easily be converted to a $co-SAT$ oracle by simply flipping the answer. \section{P-Completeness and the Circuit Value Problem} A language $L$ is said to be {\sl P-complete} under {\sl logspace mapping reductions} if: \begin{enumerate} \item $L \in P$ \item For all languages $A \in P,$ there exists a logspace bounded Turing Machine with a read-only input tape, a write-only output tape, and a read/write work tape, that computes a function $f$ such that: $x \in A \Longleftrightarrow f(x) \in L$. \end{enumerate} One reason why we are interested in P-complete problems is that we believe they are difficult to compute on a parallel machine. There are many known P-complete problems. We will be interested in the {\sl Circuit Value Problem (CVAL)}. In the Circuit Value Problem, we are given both the description of a circuit and inputs to the circuit, and we are asked to determine the output of the circuit on those particular inputs. It's not hard to see that this can be done in polynomial time. We conjecture, however, that it's hard to come up with an efficient parallel solution. We will now argue that the CVAL is P-complete under logspace reductions. The following argument is meant to be a proof sketch, and is by no means rigorous. First of all, it's not hard to see that the problem is in \p . Now, we must show that for every polynomial time bounded TM $M$, we can construct a logspace computable function $f$ that takes as input $\bar{x}$ and outputs a circuit $C$ and an assinment to the inputs $\bar{y}$ such that $C(\bar{y})$ accepts if and only if $M$ accepts $\bar{x}$ (in polynomial time). Our construction will be similar to the Cook-Levin construction for the NP-completeness of SAT. Let $t(n)$ be a bound on the running time of $M$. Assume without loss of generality, that when $M$ is about to accept (reject), it erases its tape, moves its read head all the way to the left, and enters its accept (reject) state. Moreover, $M$ will continue to stay in the same configuration until it has executed $t(n)$ steps. We will make a $t(n) \times t(n)$ table $c$, where $c_{i,t}$ consists of the contents of cell $i$ of $M$'s configuration at time $t$. Now, $c_{i,t}$ only depends on a fixed number of entries in from the $(t-1)$st row. So, we will have for each $i$ and $t$ a circuit segment (of constant size) which computes $c_{i,t}$ from those inputs. We want the output of our main circuit to be $c_{1, t(n)}.$ It is easy to construct such a circuit $C$ which computes $c_{1, t(n)}$ by cascading the small circuit segments defined above. This circuit can be produced by a logspace Turing Machine since the structure is repetitive. $QED$ \end{document}