Recitation 7 latex source
This file is provided to help students create crib sheets
in latex if they wish. Some formatting was removed for clarity.
It is missing some macros, but you can figure out what they are
by looking at the pdf image. It is not a working latex file.
\begin{document}
\newtheorem{thm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{asmp}[thm]{Assumption}
\newtheorem{claim}[thm]{Claim}
\newtheorem{conj}[thm]{Conjecture}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{ques}[thm]{Question}
\newtheorem{example}[thm]{Example}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\EE}{\mathbb{E}}
\newcommand{\EEE}{\mathop{\mathbb{E}}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
% \newcommand{\C}{\mathbb C}
\newcommand{\D}{\mathbb D}
\newcommand{\E}{\mathbb E}
\newcommand{\F}{\mathbb F}
\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\chapter{Recitation 08: P, NP, Dynamic Programming}
This recitation covers some basic definitions and tools of complexity theory.
In the first half of the semester, we learned about computability theory, where we placed languages in classes (regular, context-free, decidable, T-recognizable) based on whether they could be solved using certain models of computation. We now move on to complexity theory, where we restrict our attention to \textit{decidable} languages and first focus on determining how much \textit{time} is required to decide them.
\section{Time complexity for deterministic models}
To determine the time complexity of a language, we first define what it means for a Turing machine to run in $t(n)$ time, where $t: \N \rightarrow \N$.
\begin{defn} \label{defn:det_run}
A single-tape deterministic TM $M$ runs in time $t(n)$ if $M$ halts in at most $t(n)$ steps on all inputs of length $n$.
\end{defn}
\begin{defn} \label{defn:TIME}
$TIME(t(n)) = \{ B \,|$ some single-tape deterministic TM $M$ runs in $O(t(n))$ time and $L(M) = B \}$.
\marginnote{A TM runs in $O(t(n))$ time if it runs in $\le ct(n)$ time for some constant $c>0$ independent of $n$.}
\end{defn}
We can now define our first time complexity class.
\begin{defn} \label{defn:P}
$P=\bigcup_{k\in \N} TIME(n^k)$.
\end{defn}
In words, $P$ is the set of languages that can be decided in $cn^k$ time for constants $c, k$. These are the languages that can be decided in \textit{polynomial time}. To show that a language is in $P$, we typically must construct a TM that decides that language, then argue that the TM halts in polynomial time.
\subsection{Model independence}
While Definitions \ref{defn:det_run} and \ref{defn:TIME} require a single-tape deterministic TM, Definition \ref{defn:P} is \textit{model independent}. This means that for all reasonable deterministic models of computation, $P$ defines the same class of languages. This is useful because we are not restricted to any specific deterministic model when proving languages are in $P$.
\section{Time complexity for nondeterministic models}
We define the analogous terms for nondeterministic TMs.
\begin{defn} \label{defn:nondet_run}
A nondeterministic TM $N$ runs in time $t(n)$ if all of the threads of $N$ halt in at most $t(n)$ steps on all inputs of length $n$.
\marginnote{Note the difference between acceptance and runtime: for an NTM to accept an input, it is enough for one thread to accept. For an NTM to run in time $t(n)$, \textit{all} threads need to halt in that time.}
\end{defn}
\begin{defn} \label{defn:NTIME}
$NTIME(t(n)) = \{ B \,|$ some NTM $N$ runs in $O(t(n))$ time and $L(N) = B \}$.
\end{defn}
Intuitively, this means that the tree consisting of all the branches of $N$'s computation can have \textit{height} at most $t(n)$, as shown below. Note however that these definitions do not limit the \textit{width} of the tree, and there could be a non-polynomial number of branches, as long as each branch has polynomial length.
\vspace{1em}
\begin{tikzpicture}
% Root node
\node[circle, draw, fill=black, inner sep=1pt, label=above:Start] (root) at (0,0) {};
% First branching level
\node[circle, draw, fill=black, inner sep=1pt] (a1) at (-2, -1) {};
\node[circle, draw, fill=black, inner sep=1pt] (a2) at (0, -1) {};
\node[circle, draw, fill=black, inner sep=1pt] (a3) at (2, -1) {};
\draw (root) -- (a1);
\draw (root) -- (a2);
\draw (root) -- (a3);
% Second branching level
\node[circle, draw, fill=black, inner sep=1pt] (b1) at (-3, -2) {};
\node[circle, draw, fill=black, inner sep=1pt, label=below:Halt] (b5) at (-2.2, -2) {};
\node[circle, draw, fill=black, inner sep=1pt] (b2) at (-1, -2) {};
\node[circle, draw, fill=black, inner sep=1pt] (b3) at (1, -2) {};
\node[circle, draw, fill=black, inner sep=1pt] (b4) at (3, -2) {};
\draw (a1) -- (b1);
\draw (a1) -- (b2);
\draw (a1) -- (b5);
\draw (a2) -- (b3);
\draw (a3) -- (b4);
% Vertical dots for middle section
\node at (0, -2.75) {\vdots};
% Second-to-last branching level
\node[circle, draw, fill=black, inner sep=1pt] (d1) at (-3.5, -3.5) {};
\node[circle, draw, fill=black, inner sep=1pt] (d2) at (-2.5, -3.5) {};
\node[circle, draw, fill=black, inner sep=1pt, label=below:Halt] (d5) at (-1, -3.5) {};
\node[circle, draw, fill=black, inner sep=1pt, label=below:Halt] (d6) at (0, -3.5) {};
\node[circle, draw, fill=black, inner sep=1pt] (d3) at (2.5, -3.5) {};
\node[circle, draw, fill=black, inner sep=1pt] (d4) at (3.5, -3.5) {};
\draw[dotted] (b1) -- (d1);
\draw[dotted] (b2) -- (d2);
\draw[dotted] (b2) -- (d5);
\draw[dotted] (b3) -- (d6);
\draw[dotted] (b3) -- (d3);
\draw[dotted] (b4) -- (d4);
% Last branching level
\node[circle, draw, fill=black, inner sep=1pt, label=below:Halt] (e1) at (-4, -4.5) {};
\node[circle, draw, fill=black, inner sep=1pt, label=below:Halt] (e2) at (-3, -4.5) {};
\node[circle, draw, fill=black, inner sep=1pt, label=below:Halt] (e3) at (-2, -4.5) {};
\node[circle, draw, fill=black, inner sep=1pt, label=below:Halt] (e4) at (2, -4.5) {};
\node[circle, draw, fill=black, inner sep=1pt, label=below:Halt] (e5) at (4, -4.5) {};
\draw (d1) -- (e1);
\draw (d1) -- (e2);
\draw (d2) -- (e3);
\draw (d3) -- (e4);
\draw (d4) -- (e5);
% Label the height of the tree
\draw[<->] (4.5, 0) -- (4.5, -4.5);
\node[right] at (4.6, -2.25) {$t(n)$};
\end{tikzpicture}
\begin{defn} \label{defn:NP}
$NP=\bigcup_{k\in \N} NTIME(n^k)$.
\end{defn}
In words, $NP$ is the set of languages decided by some NTM in polynomial time. This definition is again model independent for all reasonable nondeterministic models of computation.
\subsection{Certificates for NP}
Intuitively, $NP$ consists of languages $L$ for which we can \emph{verify membership quickly}. For an input $x \in L$, there is some short ``certificate'' $c$ such that if given $c$, it is easy to confirm that $x$ is in $L$. \marginnote{Here, ``short,'' ``quickly,'' and ``easy'' all mean polynomial in $|x|$.} Here are some examples of certificates for instances of languages in $NP$:
\begin{itemize}
\item If a graph $G \in HAMPATH$, the certificate would be the sequence of nodes corresponding to the Hamiltonian path in $G$. It is certainly polynomial time to check that each node in the sequence is in $G$, all nodes in $G$ appear in the sequence exactly once, and all pairs of adjacent nodes in the sequence are connected by an edge in $G$.
\item For the $SUBSET$-$SUM$ language, defined as $\{\langle S, t\rangle \,|\, S = \{x_1,...,x_k \}$ and $\exists \{y_1,...,y_l\} \subseteq S$ such that $\sum_{i=1}^l y_i = t\}$, the certificate would be $c = \{y_1, ..., y_l\}$. Given $c$, it is easy to check that $c \subseteq S$ and that the sum of the elements of $c$ is $t$.
\end{itemize}
This concept can be formalized with the following theorem.
\begin{thm} \label{thm:certificate}
$L\in NP \Longleftrightarrow$ there exists verifier TM $V$ such that $L(V) \in P$ and ($x \in L \iff$ there exists $c$ such that $|c| = O(poly(|x|))$ and $\langle x, c\rangle \in V$).
\end{thm}
\begin{proof}
Informally, we want to show that $L\in NP \Longleftrightarrow$ strings in $L$ have short and quickly checkable certificates, and strings not in $L$ don't.
$(\Longrightarrow)$ Let $L \in NP$. Then, there exists NTM $N$ that decides $L$ in polynomial time. We will show that strings in $L$ have short and quickly checkable certificates. Construct TM $V$ which takes in $\langle x, c \rangle$ and accepts iff $c$ is an accepting computation history of $N$ on $x$.
\marginnote{Intuitively, think of the computation history as all the nondeterministic choices that $N$ made on an input. These choices specify a thread, and $V$ just needs to check whether this thread leads to an accept state.}
From our previous algorithms for checking that computation histories are valid and accepting, we know that $V$ runs in polynomial time. Then, for all $x\in L$, let $c$ be the computation history of $N$ on $x$. We know that $c$ is short since $N$ runs in polynomial time.
$(\Longleftarrow)$ Let language $L$ have short and quickly checkable certificates for strings in $L$. We will show that $L\in NP$. Let $V$ be the verifier for $L$ that runs in time $n^k$ for inputs of length $n$, for some constant $k$. For an input $x$ of length $n$, since $V$ accepts $\langle x, c\rangle$ for some certificate $c$ in time $n^k$, we know that $|c|$ won't exceed $n^k$. We can thus build NTM $N$: on input $x$, nondeterministically guess certificate $c$ of length at most $n^k$. Run $V$ on $\langle x, c\rangle$ and accept if and only if $V$ accepts.
\marginnote{A small detail on guessing: since a TM a fixed number of states, we
can't guess the entire $c$ all at once (since the number of possibilities
may depend on $n$). Instead we can guess $c$ bit-by-bit.}
$N$ will accept $x$ if and only if there exists a $c$ such that $V$ accepts $\langle x, c \rangle$, so $L(N) = L$. All threads will halt in polynomial time since $|c|$ is polynomial, and $V$ runs in polynomial time.
\end{proof}
Given Theorem \ref{thm:certificate}, it is now easy to show that a language $L\in NP$. To construct an NTM running in polynomial time that decides $L$, we can
\begin{enumerate}
\item Think of a (short, easy to check) certificate for strings in $L$.
\item Build the following NTM. On input $x$:
\begin{enumerate}
\item Guess the certificate $c$.
\item Check whether or not $c$ is a valid certificate for $x$. Accept if so. Else, reject.
\end{enumerate}
\end{enumerate}
\section{Dynamic programming}
Dynamic programming is a tool to show that languages are in $P$. Sometimes, the brute-force algorithm for a problem is non-polynomial, but using dynamic programming, we can solve it in polynomial time. Dynamic programming is applicable when the problem has the following two properties:
\begin{itemize}
\item \textbf{Recursive:} The answer for a problem can be computed from answers of smaller subproblems that can be solved in the same way.
\item \textbf{Memory:} The total number of different subproblems is polynomial.
\end{itemize}
\marginnote{A simple application of dynamic programming is in computing the $n$-th term of the Fibonacci sequence ($0, 1, 1, 2, 3, 5, ...$). The $n$-th term $f(n)$ is equal to $f(n-1) + f(n-2)$, with $f(0) = 0, f(1) = 1$. How many steps would be required if the algorithm were purely recursive? How about if we use dynamic programming?}
The first property guarantees that dynamic programming works, and the second property guarantees that the runtime is polynomial. Dynamic programming is essentially a recursive algorithm that \textit{memoizes} (remembers) the answers of solved subproblems, so each subproblem is solved only once. The recursive approach is referred to as the \emph{top-down approach}.
An often cleaner way to design dynamic programming solutions is the \emph{bottom-up approach}. In this approach, subproblems are sorted in order of size, and each is computed one-by-one. Each time a subproblem is encountered, the answer can be directly computed, since the answers to the smaller subproblems have already been computed and stored.
\marginnote{The top-down approach has the advantage that it doesn't compute the answers to subproblems that are not used, but its runtime is often harder to reason about. The bottom-up approach may do redundant work since it solves \textit{all} subproblems.}
The following example illustrates the bottom-up approach.
\begin{prop}
The class $P$ is closed under $*$. More precisely, $A\in P \Longrightarrow A^* \in P$.
\end{prop}
Recall that $A^* = \{ w \,|\, w = x_1x_2\cdots x_k, x_i\in A, k\geq 0 \}$. The brute-force solution would be to try all possible splits of $w$ into $x_1x_2\cdots x_k$, for all $k = 1, ... n$. However, this is not solvable in polynomial time, since there are exponentially many possible ways to split $w$. Instead, we use dynamic programming.
\begin{proof}[Proof idea]\let\qed\relax
Let $A$ be recognized by TM $M$ in polynomial time. We want to construct TM $N$ recognizing $A^*$ in polynomial time.
On an input $w$ of length $n$, checking whether $w\in A^*$ can be done recursively. More precisely, $w\in A^*$ if and only if at least one of the following two conditions holds:
\begin{itemize}
\item $w\in A$ or $w=\epsilon$
\item There exists $i$, $1\le i < n$, such that $w_{[1\ldots i]} \in A^*$ and $w_{[i+1\ldots n]} \in A^*$ \marginnote{Let $w = w_1w_2 \cdots w_n$. Here, we are using $w_{[l\ldots r]}$ to denote substring $w_lw_{l+1} \cdots w_r$. }
\end{itemize}
With the properties above, we can determine whether $w \in A^*$ from the answers to the subproblems for $w_{[1\ldots i]}$ and $w_{[i+1\ldots n]}$. Thus, the problem has the recursive property.
For the memory property, we want to bound the total number of different subproblems. Each subproblem will correspond to a substring $w_{[l \ldots r]}$. There are $O(n^2)$ ways to choose $l$ and $r$, so there are polynomially many subproblems. To solve each subproblem, we try all possible values of $i$, for $1 \leq i < n$, so we use $2 (n-1) = O(n)$ subproblems to compute the answer. This shows that the total runtime $(O(n^2) \cdot O(n))$ is polynomial.
\end{proof}
\begin{proof}
We will use the bottom-up approach of dynamic programming.
Build TM $N$ recognizing $A^*$ as follows:
\begin{itemize}
\item On input $w$, accept if $x=\epsilon$. Otherwise, consider the subproblems ``is $w_{[l\ldots r]} \in A^*$?'' for all $1 \leq l \leq r < n$. Sort the $O(n^2)$ subproblems by length (i.e., $r-l+1$).
\item To solve the problem for $w_{l\cdots r}$, we first check if $w_{[l\ldots r]}\in A$ and answer Y if so. Otherwise, we answer Y to $w_{l\cdots r}$ if $w_{[l\ldots i]} \in A^*$ and $w_{[i+1\ldots r]} \in A^*$ for any $i$, where $i = l, l+1, ..., r-1$. If not, answer N.
\item If the answer for $w_{1 \ldots n}$ (the largest and final subproblem) is Y, accept. Otherwise, reject.
\end{itemize}
See the proof idea above for the analysis of why $N$ runs in polynomial time. We thus have $A^* \in P$.
\end{proof}
Consider a simple example, where $A = \{a, ab\}$, and $w = abaaba$. We have that $w \in A^*$ using the following split: $ab | a | ab | a$. The visual depiction below shows a snapshot of $N$'s memory while following the dynamic programming solution detailed above.
\vspace{1em}
\begin{center}
\begin{tikzpicture}
\def\n{6} % Size of the table
% Draw the grid
\foreach \i in {0,...,\n} {
\draw (\i, 0) -- (\i, \n);
\draw (0, \i) -- (\n, \i);
}
% Highlight answer cell and grey out unused cells
\fill[blue!20] (0, \n-1) rectangle (1, \n);
\node at (0.5, \n-0.5) {\footnotesize \textbf{Answer}};
\foreach \i in {2,...,\n} {
\foreach \j in {2, ..., \i} {
\fill[lightgray!] (\i-1, \j-2) rectangle (\i, \j-1);
}
}
% Fill in answers to some subproblems
\node at (0.5, 0.5) {\footnotesize Y};
\node at (1.5, 1.5) {\footnotesize N};
\node at (2.5, 2.5) {\footnotesize Y};
\node at (3.5, 3.5) {\footnotesize Y};
\node at (4.5, 4.5) {\footnotesize N};
\node at (5.5, 5.5) {\footnotesize Y};
\node at (0.5, 1.5) {\footnotesize Y};
\node at (1.5, 2.5) {\footnotesize N};
\node at (2.5, 3.5) {\footnotesize Y};
% Label axes
\node[below] at (3, -0.5) {Start index $l$};
\node[rotate=90] at (-0.7, 3) {End index $r$};
\foreach \j in {1,...,\n} {
\node at (\j-0.5, -0.3) {\footnotesize $\j$};
}
\foreach \i in {1,...,\n} {
\node at (-0.3, \i-0.5) {\footnotesize $\i$};
}
\end{tikzpicture}
\end{center}