\documentclass[12pt, oneside]{article}
\usepackage[letterpaper, scale=0.89, centering]{geometry}
\usepackage{fancyhdr}
\setlength{\parindent}{0em}
\setlength{\parskip}{1em}
\usepackage{tikz}
\usetikzlibrary{automata,positioning,arrows}
\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: Time Complexity}
In practice, computers (and Turing machines) don't have infinite tape,
and we can't afford to wait unboundedly long for an answer.
``Decidable" isn't good enough - we want ``Efficiently decidable".
For a given algorithm working on a given input, how long do we need to wait for an answer?
How does the running time depend on the input in the worst-case? average-case?
We expect to have to spend more time on computations with larger inputs.
A language is {\bf recognizable} if \underline{\phantom{\hspace{4.5in}}}
A language is {\bf decidable} if \underline{\phantom{\hspace{4.7in}}}
A language is {\bf efficiently decidable} if \underline{\phantom{\hspace{4in}}}
A function is {\bf computable} if \underline{\phantom{\hspace{4.7in}}}
A function is {\bf efficiently computable} if \underline{\phantom{\hspace{4in}}}\\
\vfill
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$}
\]
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))$} \}
\]
An example of an element of $TIME( 1 )$ is
An example of an element of $TIME( n )$ is
Note: $TIME( 1) \subseteq TIME (n) \subseteq TIME(n^2)$
\vfill
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)
\]
{\it Compare to exponential time: brute-force search.}
Theorem (Sipser 7.8): Let $t(n)$ be a function with $t(n) \geq n$. Then every $t(n)$ time deterministic
multitape Turing machine has an equivalent $O(t^2(n))$ time deterministic 1-tape Turing machine.
\newpage
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$}
\]
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))$} \}
\]
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 TIME(n^2)$
\vfill
{\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.
\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
\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}
{\bf} Notice: $NP \subseteq \{ L \mid L \text{ is decidable} \}$ so $A_{TM} \notin NP$
\vfill
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
\newpage
\subsection*{Wednesday: P vs. NP}
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 string in $3SAT$
\[
\langle (x \vee \bar{y} \vee {\bar z}) \wedge (\bar{x} \vee y \vee z) \wedge (x \vee y \vee z) \rangle
\]
Example string not in $3SAT$
\[
\langle (x \vee y \vee z) \wedge
(x \vee y \vee{\bar z}) \wedge
(x \vee \bar{y} \vee z) \wedge
(x \vee \bar{y} \vee \bar{z}) \wedge
(\bar{x} \vee y \vee z) \wedge
(\bar{x} \vee y \vee{\bar z}) \wedge
(\bar{x} \vee \bar{y} \vee z) \wedge
(\bar{x} \vee \bar{y} \vee \bar{z}) \rangle
\]
{\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 string in $CLIQUE$
\vfill
Example string 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
\vfill
\vfill
\newpage
\newpage
\subsection*{Friday: Review}
\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
\begin{center}
\includegraphics[width=5in]{../../resources/images/wood-951875_960_720.jpeg}
\end{center}
\subsection*{Week 10 at a glance}
\subsubsection*{Textbook reading: Chapter 7}
{\it For Monday}: Definition 7.1 (page 276)
{\it For Wednesday}: Definition 7.7 (page 279)
\subsubsection*{Make sure you can:}
\begin{itemize}
\item Classify the computational complexity of a set of strings by determining whether it is decidable or undecidable and recognizable or unrecognizable.
\begin{itemize}
\item Distinguish between computability and complexity
\item Articulate motivating questions of complexity
\item Define NP-completeness
\item Give examples of PTIME-decidable, NPTIME-decidable, and NP-complete problems
\end{itemize}
\item Use mapping reduction to deduce the complexity of a language by comparing to the complexity of another.
\begin{itemize}
\item Distinguish between computability and complexity
\item Articulate motivating questions of complexity
\item Use appropriate reduction (e.g. mapping, Turing, polynomial-time) to deduce the complexity of a language by comparing to the complexity of another.
\item Use polynomial-time reduction to prove NP-completeness
\end{itemize}
\end{itemize}
\begin{comment}
\end{comment}
\subsubsection*{TODO:}
\begin{list}
{\itemsep2pt}
\item Student Evaluations of Teaching forms: Evaluations are open for completion anytime BEFORE 8AM on Saturday, March 16.
Access your SETs from the Evaluations site
\begin{quote}
\url{https://academicaffairs.ucsd.edu/Modules/Evals}
\end{quote}
You will separately evaluate each of your listed instructors for each enrolled course.
**NEW** WINTER 2024 SET INCENTIVE LOTTERY: In Winter 2024, students who complete all of their student
evaluation forms for their undergraduate course will be entered into a lottery to win one of
5 \$100 Visa gift cards! To be entered into the lottery, students must complete at
least one instructor evaluation for EACH of their undergraduate courses.
They will be automatically entered when they have completed an instructor evaluation for
all of their undergraduate courses.
\item Review quizzes based on class material each day; review quiz for Friday includes opportunity for feedback for course.
\item Homework assignment 5 due Thursday.
\end{list}
\end{document}