\documentclass[ignorenonframetext,11pt]{beamer}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}
\usepackage{url}
\usepackage{textcomp}
\mode<presentation>
{ \usetheme{Malmoe}  % another good theme:   
  %\usetheme{Madrid} 
  \useinnertheme{circles}
  \setbeamertemplate{bibliography item}[text] 
  \setcounter{secnumdepth}{-1}
  \definecolor{uofsgreen}{rgb}{.125,.5,.25}
  \usecolortheme[named=uofsgreen]{structure}
}

\title[NP-Completeness]{Time to learn about NP-completeness!}
\author[Craig Weidert]{Craig Weidert}
\date{\today}
\institute{Harvey Mudd College}

\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Om}{\Omega}
\newcommand{\BO}{\mathcal{O}}
\newcommand{\Pe}{\mathcal{P}}
\newcommand{\NP}{\mathcal{NP}}
\newcommand{\ds}{\displaystyle}

\begin{document}

\section{Introduction}

\begin{frame}
\maketitle
\end{frame}

\begin{frame}
\frametitle{Languages}
\begin{itemize}
\item A language is a set of strings
\item Examples
	\begin{itemize}
	\item The language of strings of all ``a''s with odd length
	\item The language of strings with the same number of ``a''s and ``b''s
	\end{itemize}
\pause
\item If we can figure out whether to accept or reject any particular string as part of a language, we say that that language is \emph{decidable}.  
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Turing Machines}
\begin{itemize}
\item One convenient computation model:  The Turing Machine
	\begin{itemize}
	\item Tape containing symbols from an alphabet
	\item States %(including start and final states)
	\item Transition rules %(based on input it sees, tells machine what to write and how to move)
	\end{itemize}
\item Example:  a Turing Machine that decides the language of strings of ``a''s with odd length.  

\begin{columns}
\begin{column}{40mm}
\includegraphics[scale=.5]{odd2}
\end{column}
\begin{column}{50mm}
\begin{tabular}{|c|c|c|c|c|c|c|c}
\hline
\# & a & a & a & a & a & \# & \dots \\
\hline
\end{tabular}
\end{column}
\end{columns}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Non-Deterministic Turing Machines}
\begin{itemize}
\item Instead of a having just one transition rule per state per symbol read on the tape, it may have many
\item Allows branching (like running many machines in parallel)
\item If any branch reaches the accepting state, then the machine accepts the string
\end{itemize}
\end{frame}

\begin{frame} 
\frametitle{Time Complexity}
\begin{itemize}
\item Big-Oh notation
	\begin{itemize}
	\item Counting your toes takes $\BO(\textrm{number of toes})$ time.  
	\item Adding two $n$ bit numbers takes $\BO(n)$ time.  
	\item Multiplying two $n \times n$ matrices takes $\BO(n^3)$ time.  
	\end{itemize}
\item Language is polynomial time decidable if any string is either accepted or rejected in time proportional to some polynomial in the size of the string
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Polynomial Time Reducibility}
\begin{itemize}
\item Language A is reducible to language B if there is some mapping from strings to strings such the first string is in language A iff the mapping of that string is in language B.  
\item Silly Example:  the language of strings of odd length can be reduced to the language of strings of even length 
\item Complicated Example:  From the last talk, 3-SAT can be reduced to Graph 3-Colorability
\pause
\item If you can perform this reduction in polynomial time, A is polynomial time reducible to B.  
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{$\Pe$ vs $\NP$}
\begin{itemize}
\item $\Pe$ is the class of languages which can be decided in polynomial time by a deterministic Turing Machine
\item $\NP$ is the class of languages which can be decided in polynomial time by a non-deterministic Turing Machine
\item Equivalently, $\NP$ is the class of languages which can be verified in polynomial time
\item $\Pe \subseteq \NP$  
\pause
\item $\Pe = \NP$?
		\begin{itemize}
		\item Worth \$1,000,000
		\end{itemize}
\end{itemize}
\end{frame}



\section{NP-Completeness}

\begin{frame}
\frametitle{NP-Completeness}
\begin{itemize}
\item Two requirements for a language to be $\NP$-complete
	\begin{itemize}
	\item The language must be in $\NP$
	\item Any other language in $\NP$ is polynomial time reducible to that language
	\end{itemize}
\pause
\item Implications of $\NP$-completeness
	\begin{itemize}
	\item Polynomial time algorithm for any $\NP$-complete language yields a polynomial time algorithm for all languages in $\NP$ and means that $\Pe = \NP$.  
	\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{SAT Review}
\begin{itemize}
\item Variables may either be true or false.  
\item Variables may be NOTed (with $\neg$), ORed (with $\vee$), or ANDed (with $\wedge$).  
\item Example formula:  $(a \vee \neg b \vee c \vee \neg d) \wedge (\neg a \vee c \vee d)$  
\item SAT is the language which is a collection of formulas such that there is some assignment of variables that makes the formula true.  
\end{itemize}
\end{frame}



\section{Cook's Theorem}

\begin{frame}
\frametitle{Cook's Theorem - SAT is $\NP$-complete}
\begin{itemize}
\item SAT $\in \NP$:  easy to verify given a correct assignment of variables
\item Need to show that any language B in NP can be reduced in polynomial time to SAT
	\begin{itemize}
	\item Language B can be decided by a non-deterministic Turing Machine in $n^k$ time for some constant $k$.  
	\item We can build a huge formula to simulate a Turing Machine running on a string to decide whether it's in language B.  
	\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Tableau}
\begin{tabular}{|c|c|c|c|c|l}
\cline{1-5}
\# & $q_{\textrm{start}}$ & $w_1$ & \begin{tabular}{c|c|c|c|c|c}$w_2$&\dots&$w_l$&$\sqcup$&\dots&$\sqcup$\end{tabular} &\# & starting config.\\
\cline{1-5}
\#&&&&\# & second config.\\
\cline{1-5}
&&&&&\\
&&&\begin{tabular}{c|c|c|c|c}\cline{2-4} & \phantom{$\sqcup$}& \phantom{$\sqcup$}& \phantom{$\sqcup$}& \\ \cline{2-4} & & & & \\ \cline{2-4} \end{tabular}&&\\
&&&&&\\
\cline{1-5}
\#&&&&\# & $n^k$th config. \\
\cline{1-5}
\end{tabular}
\begin{itemize}
\item Essentially a similates of the tape and state of the Turing Machine at different steps
\item Doesn't need to be more than $n^k$ wide
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Formula Overview}
\begin{itemize}
\item Variables for each possible symbol in cell of tableau:  $x_{i,j,c}$
	\begin{itemize}
	\item $i$ and $j$ correspond to the row and column of the tableau
	\item $c \in [\textrm{(alphabet of TM)} \cup \textrm{(states of TM)} \cup {\#}]$ correspond to different things which may be in cells
	\end{itemize}
\item Variable is true if there that particular cell contains that particular symbol
\item Will make one massive SAT formula $\phi$ corresponding to tableau for an instance 
\item $\phi = \phi_{\textrm{cell}} \wedge \phi_{\textrm{start}} \wedge \phi_{\textrm{accept}} \wedge \phi_{\textrm{transition}}$
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Cell Subformula}
\begin{equation*}
\phi_{\textrm{cell}} = \bigwedge_{1 \leq i, j \leq n^k} \left[\left(\bigvee_{s \in C} x_{i, j, s}\right) 
\wedge \left(\bigwedge_{s, t \in C(s \neq t)} \left(\overline{x_{i, j, s}} \vee \overline{x_{i, j, t}}\right)\right)\right]
\end{equation*}
In English:  ``Every cell in the tableau must have exactly one symbol.''  
\end{frame}

\begin{frame}
\frametitle{Start and Accept Subformulas}
\begin{itemize}
\item Start subformula
	\begin{itemize}
	\item $x_{1, 1, \#} \wedge x_{1, 2, q_{\textrm{start}}} \wedge x_{1, 3, w_0} \wedge \dots \wedge x_{1, l, w_l} \wedge x_{1, l+1, \sqcup} \wedge \dots \wedge x_{1, n^k - 1, \sqcup} \wedge x_{1, n^k, \#}$
	\item In English:  ``The first row in the tableau must correspond to the input.''  
	\end{itemize}
\item Accept subformula
	\begin{itemize}
	\item \[\bigvee_{1 \leq i, j \leq n^k} x_{i, j, q_{\textrm{accept}}}\]
	\item In English:  ``Somewhere in our tableau, we have record of being in an accepting state.''
	\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Transition Subformula}
\begin{itemize}
\item Ensures that our transitions from one row to another are legal  
\item Since TM can only move one cell at a time, enough to look at all 2 $\times$ 3 windows.  \\
\includegraphics[scale =.25]{window}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Transition Subformula (cont.)}
\begin{columns}
\begin{column}{50mm}
Legal Windows
\centering 
\begin{tabular}{|c|c|c|} \hline
\# & $q_{\textrm{even}}$ & a \\ \hline
\# & a & $q_{\textrm{odd}}$ \\ \hline \end{tabular}

\begin{tabular}{|c|c|c|} \hline
\# & a & $q_{\textrm{even}}$ \\ \hline
\# & a & a \\ \hline \end{tabular}
\end{column}
\begin{column}{50mm}
Illegal Windows
\centering
\begin{tabular}{|c|c|c|} \hline
\# & $q_{\textrm{even}}$ & a \\ \hline
\# & a & $q_{\textrm{even}}$ \\ \hline \end{tabular}

\begin{tabular}{|c|c|c|} \hline
\# & $q_{\textrm{even}}$ & a \\ \hline
a & a & $q_{\textrm{odd}}$ \\ \hline \end{tabular}
\end{column}
\end{columns}

\begin{equation*}
\phi_{transition} = \bigwedge_{1 < i \leq n^k, 1 < j < n^k}(\textrm{the window centered at i, j is ok})
\end{equation*}
%\begin{equation*}
%\bigvee_{\textrm{$a_k$'s make a legal window}}
%(x_{i, j-1, a_1} \wedge x_{i, j, a_2} \wedge x_{i, j+1, a_3} \wedge %x_{i+1, j-1, a_4} \wedge x_{i+1, j, a_5} \wedge x_{i+1, j+1, a_6})
%\end{equation*}
In English:  ``Make sure that all of the windows in our tableau jive with our transition states.''  
\end{frame}

\begin{frame}
\frametitle{Reduction takes Polynomial Time}
\begin{itemize}
\item $\phi = \phi_{\textrm{cell}} \wedge \phi_{\textrm{start}} \wedge \phi_{\textrm{accept}} \wedge \phi_{\textrm{transition}}$
\item Size of formula
	\begin{itemize}
	\item $\phi_{\textrm{start}}$ is size $\BO(n^k)$
	\item $\phi_{\textrm{cell}}$, $\phi_{\textrm{cell}}$, and $\phi_{\textrm{accept}}$ are all of size $\BO(n^k*n^k)$ 
	\end{itemize}
\item Formation of formula
	\begin{itemize}
	\item The formation of the formula is very repetitive  
	\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Proof Review}
\begin{itemize}
\item SAT is in $\NP$
\item Any language in $\NP$ is polynomial time reducible to SAT
	\begin{itemize}
	\item Languages in $\NP$ are decidable by a non-deterministic Turing Machine in polynomial time
	\item Can reduce this machine's running into a formula 
	\item Formula $\phi = \phi_{\textrm{start}} \wedge \phi_{\textrm{cell}} \wedge \phi_{\textrm{transition}} \wedge \phi_{\textrm{accept}}$ is satisfiable iff Turing Machine can run to acceptance 
	\item Reduction in polynomial time
	\end{itemize}
\pause
\item So, SAT is $\NP$-complete!
\end{itemize}
\end{frame}


\section{Bonus}

\begin{frame}
\frametitle{3-SAT $\NP$-Complete}
\begin{itemize}
\item Now that we know SAT is $\NP$-complete, to show that another is $\NP$-complete, we only have to show that 
	\begin{itemize}
	\item it's in $\NP$ and
	\item that we can reduce SAT to it in polynomial time
	\end{itemize}
\item 3-SAT is $\NP$-Complete
	\begin{itemize}
	\item 3-SAT is verifiable in polynomial time
	\item For every clause $(a_1 \vee a_2 \vee \dots \vee a_l)$ in SAT, make the clauses $(a_1 \vee a_2 \vee z_1) \wedge (\neg z_1 \vee a_3 \vee z_2) \wedge \dots \wedge (\neg z_{l - 3} \vee a_{l-1} \vee a_l)$ in 3-SAT
	\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
Presentation based on the proof from Prof.~Pippenger's Complexity Theory class and Cook's Theorem in Michael Sipser's ``Introduction to the Theory of Compuation'' 2nd ed. 2006.  
\end{frame}

\end{document}