Recall Definition (Sipser 7.1): For \(M\) a deterministic decider, its
**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 **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 **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 **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)\]

**True** or
**False**: \(TIME(n^2) \subseteq NTIME(n^2)\)

**True** or
**False**: \(NTIME(n^2) \subseteq DTIME(n^2)\)

**Examples in \(P\)**

*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\).

**Examples in \(NP\)**

*“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}\}\]

**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.

Problems in \(P\) |
Problems in \(NP\) |
---|---|

(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\) |

Million-dollar question: Is \(P = NP\)?

One approach to trying to answer it is to look for
*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.

Please complete the review quiz questions on Gradescope about complexity (\(P\) and \(NP\))

Definition (Sipser 7.29) Language \(A\) is **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\).

**Theorem** (Sipser 7.31): If \(A \leq_P B\) and \(B \in P\) then \(A \in P\).

Proof:

Definition (Sipser 7.34; based in Stephen Cook and Leonid Levin’s
work in the 1970s): A language \(B\) is
**NP-complete** means (1) \(B\) is in NP
**and** (2) every language \(A\) in \(NP\) is polynomial time reducible to \(B\).

**Theorem** (Sipser 7.35): If \(B\) is NP-complete and \(B \in P\) then \(P = NP\).

Proof:

**3SAT**: A literal is a Boolean variable
(e.g. \(x\)) or a negated Boolean
variable (e.g. \(\bar{x}\)). A Boolean
formula is a **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\)

Example strings not in \(3SAT\)

**Cook-Levin Theorem**: \(3SAT\) is \(NP\)-complete.

*Are there other \(NP\)-complete problems?* To
prove that \(X\) is \(NP\)-complete

*From scratch*: prove \(X\) is in \(NP\) and that all \(NP\) problems are polynomial-time reducible to \(X\).*Using reduction*: prove \(X\) is in \(NP\) and that a known-to-be \(NP\)-complete problem is polynomial-time reducible to \(X\).

**CLIQUE**: A **\(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\)

Example strings not in \(CLIQUE\)

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

vertices for two literals in the same clause

vertices for literals that are negations of one another

Example: \((x \vee \bar{y} \vee {\bar z}) \wedge (\bar{x} \vee y \vee z) \wedge (x \vee y \vee z)\)

Please complete the review quiz questions on Gradescope about complexity (\(NP\)-completeness)

Model of
Computation |
Class of
Languages |

Deterministic finite
automata: formal definition, how to design for a given
language, how to describe language of a machine?
Nondeterministic finite automata: formal
definition, how to design for a given language, how to describe language
of a machine? Regular expressions: formal
definition, how to design for a given language, how to describe language
of expression? Also: converting between different
models. |
Class of regular
languages: what are the closure properties of this
class? which languages are not in the class? using pumping
lemma to prove nonregularity. |

Push-down
automata: formal definition, how to design for a given
language, how to describe language of a machine?
Context-free grammars: formal definition,
how to design for a given language, how to describe language of a
grammar? |
Class of context-free
languages: what are the closure properties of this
class? which languages are not in the class? |

Turing machines that always halt in polynomial time | \(P\) |

Nondeterministic Turing machines that always halt in polynomial time | \(NP\) |

Deciders
(Turing machines that always halt): formal definition, how to design for
a given language, how to describe language of a machine? |
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 |

Turing
machines formal definition, how to design for a given
language, how to describe language of a machine? |
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 |

**Given a language, prove it is
regular**

*Strategy 1*: construct DFA recognizing the
language and prove it works.

*Strategy 2*: construct NFA recognizing the
language and prove it works.

*Strategy 3*: construct regular expression
recognizing the language and prove it works.

*“Prove it works” means …*

**Example**: \(L = \{ w \in \{0,1\}^* \mid \textrm{$w$ has odd
number of $1$s or starts with $0$}\}\)

Using NFA

Using regular expressions

**Example**: Select all and only the
options that result in a true statement: “To show a language \(A\) is not regular, we can…”

Show \(A\) is finite

Show there is a CFG generating \(A\)

Show \(A\) has no pumping length

Show \(A\) is undecidable

**Example**: What is the language generated
by the CFG with rules \[\begin{aligned}
S &\to aSb \mid bY \mid Ya \\
Y &\to bY \mid Ya \mid \varepsilon
\end{aligned}\]

**Example**: Prove that the language \(T = \{ \langle M \rangle \mid \textrm{$M$ is a
Turing machine and $L(M)$ is infinite}\}\) is undecidable.

**Example**: Prove that the class of
decidable languages is closed under concatenation.

Please complete the review quiz questions on Gradescope giving feedback on the quarter. Have a great summer!