\documentclass[12pt, oneside]{article}
\usepackage[letterpaper, scale=0.89, centering]{geometry}
\usepackage{fancyhdr}
\setlength{\parindent}{0em}
\setlength{\parskip}{1em}
\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0pt}
\rfoot{\href{https://creativecommons.org/licenses/by-nc-sa/2.0/}{CC BY-NC-SA 2.0} Version \today~(\thepage)}
\usepackage{amssymb,amsmath,pifont,amsfonts,comment,enumerate,enumitem}
\usepackage{currfile,xstring,hyperref,tabularx,graphicx,wasysym}
\usepackage[labelformat=empty]{caption}
\usepackage{xcolor}
\usepackage{multicol,multirow,array,listings,tabularx,lastpage,textcomp,booktabs}
\lstnewenvironment{algorithm}[1][] {
\lstset{ mathescape=true,
frame=tB,
numbers=left,
numberstyle=\tiny,
basicstyle=\rmfamily\scriptsize,
keywordstyle=\color{black}\bfseries,
keywords={,procedure, div, for, to, input, output, return, datatype, function, in, if, else, foreach, while, begin, end, }
numbers=left,
xleftmargin=.04\textwidth,
#1
}
}
{}
\newcommand\abs[1]{\lvert~#1~\rvert}
\newcommand{\st}{\mid}
\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}
\begin{document}
\begin{flushright}
\StrBefore{\currfilename}{.}
\end{flushright}
\section*{Monday}
Recall Definition (Sipser 7.1): For $M$ a deterministic decider, its {\bf running time} is the function $f: \mathbb{N} \to \mathbb{N}$
given by
\[
f(n) = \text{max number of steps $M$ takes before halting, over all inputs of length $n$}
\]
Recall Definition (Sipser 7.7): For each function $t(n)$, the {\bf time complexity class} $TIME(t(n))$, is defined by
\[
TIME( t(n)) = \{ L \mid \text{$L$ is decidable by a Turing machine with running time in $O(t(n))$} \}
\]
Recall Definition (Sipser 7.12) : $P$ is the class of languages that are decidable in polynomial time on
a deterministic 1-tape Turing machine
\[
P = \bigcup_k TIME(n^k)
\]
Definition (Sipser 7.9): For $N$ a nodeterministic decider.
The {\bf running time} of $N$ is the function $f: \mathbb{N} \to \mathbb{N}$ given by
\[
f(n) = \text{max number of steps $N$ takes on any branch before halting, over all inputs of length $n$}
\]
Definition (Sipser 7.21): For each function $t(n)$, the {\bf nondeterministic time complexity class}
$NTIME(t(n))$, is defined by
\[
NTIME( t(n)) = \{ L \mid \text{$L$ is decidable by a nondeterministic Turing machine with running time in $O(t(n))$} \}
\]
\[
NP = \bigcup_k NTIME(n^k)
\]
{\bf True} or {\bf False}: $TIME(n^2) \subseteq NTIME(n^2)$
\vfill
{\bf True} or {\bf False}: $NTIME(n^2) \subseteq DTIME(n^2)$
\vfill
\newpage
{\bf Examples in $P$ }
{\it Can't use nondeterminism; Can use multiple tapes; Often need to be “more clever” than naïve / brute force approach}
\[
PATH = \{\langle G,s,t\rangle \mid \textrm{$G$ is digraph with $n$ nodes there is path from s to t}\}
\]
Use breadth first search to show in $P$
\[
RELPRIME = \{ \langle x,y\rangle \mid \textrm{$x$ and $y$ are relatively prime integers}\}
\]
Use Euclidean Algorithm to show in $P$
\[
L(G) = \{w \mid \textrm{$w$ is generated by $G$}\}
\]
(where $G$ is a context-free grammar). Use dynamic programming to show in $P$.
\vfill
{\bf Examples in $NP$}
{\it ``Verifiable" i.e. NP, Can be decided by a nondeterministic TM in polynomial time,
best known deterministic solution may be brute-force,
solution can be verified by a deterministic TM in polynomial time.}
\[
HAMPATH = \{\langle G,s,t \rangle \mid \textrm{$G$ is digraph with $n$ nodes, there is path
from $s$ to $t$ that goes through every node exactly once}\}
\]
\[
VERTEX-COVER = \{ \langle G,k\rangle \mid \textrm{$G$ is an undirected graph with $n$
nodes that has a $k$-node vertex cover}\}
\]
\[
CLIQUE = \{ \langle G,k\rangle \mid \textrm{$G$ is an undirected graph with $n$ nodes that has a $k$-clique}\}
\]
\[
SAT =\{ \langle X \rangle \mid \textrm{$X$ is a satisfiable Boolean formula with $n$ variables}\}
\]
\vfill
\newpage
{\bf Every problem in NP is decidable with an exponential-time algorithm}
Nondeterministic approach: guess a possible solution, verify that it works.
Brute-force (worst-case exponential time) approach: iterate over all possible solutions, for each
one, check if it works.
\begin{center}
\begin{tabular}{c|c}
{\bf Problems in $P$} & {\bf Problems in $NP$}\\
\hline
(Membership in any) regular language & Any problem in $P$ \\
(Membership in any) context-free language & \\
$A_{DFA}$ & $SAT$\\
$E_{DFA}$ & $CLIQUE$ \\
$EQ_{DFA}$ & $VERTEX-COVER$ \\
$PATH$ & $HAMPATH$ \\
$RELPRIME$ & $\ldots$ \\
$\ldots$ &\\
\end{tabular}
\end{center}
Million-dollar question: Is $P = NP$?
One approach to trying to answer it is to look for {\it hardest} problems in $NP$ and
then (1) if we can show that there are efficient algorithms for them, then we can get
efficient algorithms for all problems in $NP$ so $P = NP$, or (2) these problems might
be good candidates for showing that there are problems in $NP$ for which there
are no efficient algorithms.
\vfill
\newpage
\subsection*{Review: Week 10 Monday}
Please complete the review quiz questions on \href{http://gradescope.com}{Gradescope} about
complexity ($P$ and $NP$)
\newpage
\subsection*{Wednesday}
Definition (Sipser 7.29) Language $A$ is {\bf polynomial-time mapping reducible} to language $B$, written $A \leq_P B$,
means there is a polynomial-time computable function $f: \Sigma^* \to \Sigma^*$ such that for every $x \in \Sigma^*$
\[
x \in A \qquad \text{iff} \qquad f(x) \in B.
\]
The function $f$ is called the polynomial time reduction of $A$ to $B$.
{\bf Theorem} (Sipser 7.31): If $A \leq_P B$ and $B \in P$ then $A \in P$.
Proof:
\vfill
Definition (Sipser 7.34; based in Stephen Cook and Leonid Levin's work in the 1970s):
A language $B$ is {\bf NP-complete} means (1) $B$ is in NP {\bf and} (2) every language
$A$ in $NP$ is polynomial time reducible to $B$.
{\bf Theorem} (Sipser 7.35): If $B$ is NP-complete and $B \in P$ then $P = NP$.
Proof:
\vfill
\newpage
{\bf 3SAT}: A literal is a Boolean variable (e.g. $x$) or a negated Boolean variable (e.g. $\bar{x}$).
A Boolean formula is a {\bf 3cnf-formula} if it is a Boolean formula in conjunctive normal form (a conjunction
of disjunctive clauses of literals) and each clause has three literals.
\[
3SAT = \{ \langle \phi \rangle \mid \text{$\phi$ is a satisfiable 3cnf-formula} \}
\]
Example strings in $3SAT$
\vfill
Example strings not in $3SAT$
\vfill
{\bf Cook-Levin Theorem}: $3SAT$ is $NP$-complete.
{\it Are there other $NP$-complete problems?} To prove that $X$ is $NP$-complete
\begin{itemize}
\item {\it From scratch}: prove $X$ is in $NP$ and that all $NP$ problems are polynomial-time
reducible to $X$.
\item {\it Using reduction}: prove $X$ is in $NP$ and that a known-to-be $NP$-complete problem
is polynomial-time reducible to $X$.
\end{itemize}
\vfill
\vfill
\newpage
{\bf CLIQUE}: A {\bf $k$-clique} in an undirected graph is a maximally connected subgraph with $k$ nodes.
\[
CLIQUE = \{ \langle G, k \rangle \mid \text{$G$ is an undirected graph with a $k$-clique} \}
\]
Example strings in $CLIQUE$
\vfill
Example strings not in $CLIQUE$
\vfill
Theorem (Sipser 7.32):
\[
3SAT \leq_P CLIQUE
\]
Given a Boolean formula in conjunctive normal form with $k$ clauses and three literals per clause, we will
map it to a graph so that the graph has a clique if the original formula is satisfiable and the
graph does not have a clique if the original formula is not satisfiable.
The graph has $3k$ vertices (one for each literal in each clause) and an edge between all vertices except
\begin{itemize}
\item vertices for two literals in the same clause
\item vertices for literals that are negations of one another
\end{itemize}
Example: $(x \vee \bar{y} \vee {\bar z}) \wedge (\bar{x} \vee y \vee z) \wedge (x \vee y \vee z)$
\vfill
\newpage
\subsection*{Review: Week 10 Wednesday}
Please complete the review quiz questions on \href{http://gradescope.com}{Gradescope} about
complexity ($NP$-completeness)
\newpage
\subsection*{Friday}
\begin{center}
\begin{tabular}{|p{4in}|p{3.5in}|}
\hline
& \\
{\bf Model of Computation} & {\bf Class of Languages}\\
&\\
\hline
& \\
{\bf Deterministic finite automata}:
formal definition, how to design for a given language,
how to describe language of a machine?
{\bf Nondeterministic finite automata}:
formal definition, how to design for a given language,
how to describe language of a machine?
{\bf Regular expressions}: formal definition, how to design for a given language,
how to describe language of expression?
{\it Also}: converting between different models. &
{\bf Class of regular languages}: what are the closure
properties of this class? which languages are not in the class?
using {\bf pumping lemma} to prove nonregularity.\\
& \\
\hline
& \\
{\bf Push-down automata}:
formal definition, how to design for a given language,
how to describe language of a machine?
{\bf Context-free grammars}:
formal definition, how to design for a given language,
how to describe language of a grammar? &
{\bf Class of context-free languages}: what are the closure
properties of this class? which languages are not in the class?\\
& \\
\hline
& \\
Turing machines that always halt in polynomial time
& $P$ \\
& \\
Nondeterministic Turing machines that always halt in polynomial time
& $NP$ \\
& \\
\hline
& \\
{\bf Deciders} (Turing machines that always halt):
formal definition, how to design for a given language,
how to describe language of a machine? &
{\bf Class of decidable languages}: what are the closure properties
of this class? which languages are not in the class? using diagonalization
and mapping reduction to show undecidability \\
& \\
\hline
& \\
{\bf Turing machines}
formal definition, how to design for a given language,
how to describe language of a machine? &
{\bf Class of recognizable languages}: what are the closure properties
of this class? which languages are not in the class? using closure
and mapping reduction to show unrecognizability \\
& \\
\hline
\end{tabular}
\end{center}
\newpage
{\bf Given a language, prove it is regular}
{\it Strategy 1}: construct DFA recognizing the language and prove it works.
{\it Strategy 2}: construct NFA recognizing the language and prove it works.
{\it Strategy 3}: construct regular expression recognizing the language and prove it works.
{\it ``Prove it works'' means \ldots}
\vspace{100pt}
{\bf Example}: $L = \{ w \in \{0,1\}^* \mid \textrm{$w$ has odd number of $1$s or starts with $0$}\}$
Using NFA
\vfill
Using regular expressions
\vfill
\newpage
{\bf Example}: Select all and only the options that result in a true statement: ``To show
a language $A$ is not regular, we can\ldots''
\begin{enumerate}
\item[a.] Show $A$ is finite
\item[b.] Show there is a CFG generating $A$
\item[c.] Show $A$ has no pumping length
\item[d.] Show $A$ is undecidable
\end{enumerate}
\newpage
{\bf Example}: What is the language generated by the CFG with rules
\begin{align*}
S &\to aSb \mid bY \mid Ya \\
Y &\to bY \mid Ya \mid \varepsilon
\end{align*}
\newpage
{\bf Example}: Prove that the language
$T = \{ \langle M \rangle \mid \textrm{$M$ is a Turing machine and $L(M)$ is infinite}\}$
is undecidable.
\newpage
{\bf Example}: Prove that the class of decidable languages is closed under concatenation.
\newpage
\vfill
\begin{center}
\includegraphics[width=5in]{../../resources/images/wood-951875_960_720.jpeg}
\end{center}
\vfill
\subsection*{Review: Week 10 Friday}
Please complete the review quiz questions on \href{http://gradescope.com}{Gradescope} giving feedback on the quarter.
Have a great summer!
\end{document}