\documentclass[ignorenonframetext,11pt]{beamer} \usepackage{amsmath,amssymb} \usepackage{graphicx} \usepackage{url} \usepackage{textcomp} \mode { \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 zeros with odd length \item The language of strings with the same number of zeros and ones \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 zeros with odd length. \begin{columns} \begin{column}{40mm} \includegraphics[scale=.5]{odd} \end{column} \begin{column}{50mm} \begin{tabular}{|c|c|c|c|c|c|c|c} \hline \# & 0 & 0 & 0 & 0 & 0 & \# & \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 all zeros of odd length can be reduced to the language of strings of all zeros 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 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$? \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$. \begin{itemize} \item Worth \$1,000,000 \end{itemize} \end{itemize} \end{itemize} \end{frame} \section{Cook's Theorem} \begin{frame} \frametitle{Cook's Theorem - SAT is $\NP$-complete} \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} \begin{frame} \frametitle{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 record of the tape and state of the Turing Machine \item Doesn't need to be more than $n^k$ wide \item $\phi = \phi_{\textrm{cell}} \wedge \phi_{\textrm{start}} \wedge \phi_{\textrm{accept}} \wedge \phi_{\textrm{transition}}$ \end{itemize} \end{frame} \begin{frame} \frametitle{Proof Sketch} \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}