• Proofs, by induction especially
• CPSC 213 and 221 (kind of)
• Sets, graphs, discrete math, a little bit of linear algebra

• Assignments available on Piazza
• Assignment #1 should take an hour
• In total: 10 assignments
• Typically hard, include bonus questions
• Groups of 2 allowed
• LaTeX, Gradescope

Computational Problems. We want to understand things like: can I solve this problem? can I solve it fast?

1. ex. Given a list, sort it.
2. ex. Given an integer, find its prime factors.
3. ex. Given a polynomial, find its roots.

An alphabet is any finite non-empty set.

It is usually represented as $\Sigma$ or $\Gamma$. Often $\Sigma = \left\{ {0,1} \right\}$, or $\Sigma = \text{ASCII}$, or $\Sigma = \text{Unicode}$.

Computer science.

A string is a finite sequence of $0 +$ characters from an alphabet.

Programming.

A string is a UTF-8…

We often will talk about the empty string, so we have a special symbol for it: $\varepsilon$.

$\Sigma \ast$ is the set of all strings with alphabet $\Sigma$.

A language is any set $L$ (including infinite sets) such that $L \subset \Sigma \ast$. Even $L = \varnothing$ is okay.

A computational problem is a function mapping strings to strings.

Note that the definition of a computational problem does not specify how to produce the outputs from the inputs. There is no algorithm here.

A decision problem is a computational problem with a Boolean / binary / n-ary output.

We can usually tweak computational problems to become decision problems: e.g. given $\left( {x,y} \right)$, does $x$ have a prime factor that is $< y$?

Important Idea: decision problems are equivalent to languages.

$\left\{ {x \in \Sigma \ast :f(x) = \text{Yes}} \right\}$

reads as for all $X$ in $\Sigma \ast$ such that $f(x)$ is equal to “Yes”

Usually theorists do worst case analysis, i.e. as a function of the input length $n$, what is the maximum amount of resources used over all inputs of length $n$? (note: $n$ is a commonly used variable!)

The idea here is that it’s helpful to analyze the worst case, as every input will then result in equal or better time.

Recall: different machine models have different efficiencies: our multi-tape Turing machines were broadly more efficient than our single-tape Turing machines.

$P = \bigcup_{c > 0}\text{TIME}\left( n^{c} \right)$

Why is P a good definition for efficient computation?

• Insensitive to model of computation: by the extended Church-Turing thesis, switching computational models “only” involves a polynomial slowdown
• Closed under composition: can use polynomial time algorithm as a subroutine
• In practice: algorithms usually can be improved. If we find an $O\left( n^{30} \right)$ time algorithm, it typically can be improved to, say, $O\left( n^{5} \right)$ time.

$\text{EXP} = \bigcup_{k > 0}\text{TIME}\left( 2^{n^{k}} \right)$

The four color map works for all maps, so $\text{4COLORMAP} = \left\{ {\left\langle G \right\rangle:G\ \text{is a valid map}} \right\}$.

NP is very important! Contains a large about of natural problems.

• ex. Hamilton path, 3COLORGRAPH, graph isomorphism, satisfiable boolean formulas

Many problems in NP have “identical complexity”, i.e., are complete. (We’ll talk about this later.)

Recall:

$\text{3SAT} = \left\{ {\left\langle \varphi \right\rangle:\varphi\ \text{is a Boolean formula in CNF with 3 literals per clause for which there exists a satisfying truth assignment}} \right\}$

• e.g. $\left( {x_{1} \vee \neg x_{2} \vee x_{3}} \right) \land \left( {x_{5} \vee x_{4} \vee \neg x_{2}} \right) \land \left( {\neg x_{4} \vee x_{1} \vee x_{3}} \right) \land \left( {\neg x_{3} \vee x_{2} \land \neg x_{1}} \right)$

For some function $f:\Sigma \ast \rightarrow\Sigma \ast$, it is polytime computable if there exists a Turing machine that when given $x$ as input terminates with $f(x)$ on the tape and runs in time $\text{poly}\left( |x| \right)$.

Reductions are helpful!

• Method: find a way to map:

  • yes-instances of $P_{1}$ to yes-instances of $P_{2}$
  • no-instances of $P_{1}$ to no-instances of $P_{2}$
• Notation: $P_{1}\underset{P}{\leq}P_{2}$
• Logic: if $P_{2}$ is easy, $P_{1}$ is easy
• Contrapositive: if $P_{1}$ is hard, $P_{2}$ is hard

Theorem.

If $A\underset{P}{\leq}B$ and $B \in P$, then $A \in P$.

• There is a polytime Turing machine N that decides $B$.
• There is a polytime reduction $f$ from $A$ to $B$.

Proof.

We want a Turing machine $M$ that decides $A$ in polynomial time.

• On input $x$: compute $z = f(x)$ and then simulate $N$ on input $z$. Accept iff $N$ accepts.
• If $x \in A\Rightarrow f(x) \in B\Rightarrow N\ \text{accepts}$.
• If $x \in A^{\_}\Rightarrow f(x) \notin B\Rightarrow N\ \text{rejects}$.

When we talked about Turing machines, we had a notion of what it meant to be hard: undecidability. But now we’re talking about NP. So which problems in NP are hard?

Maybe $\text{P} = \text{NP}$, and so all problems in NP are easy.

A language $L$ is NP-complete if $L$ is NP-hard and $L \in \text{NP}$.

Theorem. Cook-Levin Theorem

SAT is NP-complete.

Corollary.

3SAT is also NP-complete.

Theorem.

If B is NP-complete, $C \in \text{NP}$, and $B\underset{P}{\leq}C$, then $C$ is NP-complete.

Proof.

• Need to show: $A\underset{P}{\leq}C,\forall A \in \text{NP}$

• We know $A\underset{P}{\leq}B$, i.e. you can solve $A$ in terms of $B$.

  • So $\exists$ a polytime computable $f:x \in A\Leftrightarrow f(x) \in B$.
• We know $B\underset{P}{\leq}C$: $\exists$ a polytime computable $g:y \in B\Leftrightarrow g(y) \in C$

• Let $h:\Sigma \ast \rightarrow\Sigma \ast$ be $h(x) = g\left( {f(x)} \right)$. This is polytime computable.

  • Has the properties: $x \in A\Leftrightarrow f(x) \in B\Leftrightarrow g(f(x) \in C$.

Problem. CLIQUE [CLIQUE]

Given $G = \left( {V,E} \right)$ and $k$, does there exist $U \subseteq V$ with $|U| \geq k$ such that $\left\{ {u,v} \right\} \in E$ for all distinct vertices $u,v \in U$?

$\text{CLIQUE} = \left\{ {\left\langle {G,K} \right\rangle:G\ \text{has a clique of size}\ k} \right\}$

• No specification on size: in our example above, there are cliques of size 0 through 3

Theorem.

CLIQUE is NP-complete: i.e. CLIQUE is NP-hard, and CLIQUE is in NP.

Proof.

CLIQUE is in NP: because there exists a verifier that can check a possible clique in polytime.

CLIQUE is NP-hard: because 3SAT (known NP-hard problem) reduces to CLIQUE. How can we do that?

Proof. $\text{3SAT}\underset{P}{\leq}\text{CLIQUE}$ (reduction)

$x \in \text{3SAT}$ maps to $f(x) \in \text{CLIQUE}$

• If $x = \left\langle \varphi \right\rangle$ where $\varphi$ is a satisfiable 3CNF formula, then $f(x) = \left\langle {G,k} \right\rangle$ where $G$ has a clique of size $k$.

$x \notin \text{3SAT}$ maps to $f(x) \notin \text{CLIQUE}$

• If $x = \left\langle \varphi \right\rangle$ where $\varphi$ has no satisfiable assignments, then $f(x) = \left\langle {G,k} \right\rangle$ where $G$ has no clique of size $k$.
• junk can map to junk

We can show 3SAT can be solved by finding a clique of size $k$.

• Connect every vertex in a block to every other vertex that is not its inverse.
• Then, every clique of size $k$ is a possible satisfiable assignment.
• We can’t have $x_{i}$ and $x_{i}^{\_}$ both being true: which is represented by no connecting edges.

We still need to “decode” $f(x) \in B$ to $x \in A$… i.e. $f(x) \in \text{CLIQUE}\Rightarrow x \in \text{3SAT}$.

• Let $U$ be a clique of size $k$. We must divy it up so that there is exactly one vertex in each group.
• Given a $f(x) \in \text{CLIQUE}$ constructed from a $\text{3SAT}$ problem, then we find a satisfying $x \in \text{3SAT}$.

Aside: suppose we want to ensure there is a clique of at least size $k - 1$. We can make a separate, disconnected clique of $k - 1$ vertices. What’s this useful for? Don’t know yet…

Main idea: an algorithm can be converted to a Boolean circuit

…table…

M accepts w if and only if the tableau can be filled such that:

• The first row is the starting configuration of M on input w
• $\left( {i + 1} \right)^{\text{st}}$ configuration follows from the $i^{\text{th}}$ configuration
• Eventually reach an accepting configuration

So how can this tableau be converted into a boolean formula? We’ll come up with some boolean variables to represent what is happening in the cells.

Let $\text{cell}\left\lbrack {i,j} \right\rbrack$ refer to the according tableau entry.

• Note: row i: time step, column j: head position, $i,j \leq n^{k}$
• Our cell entries are not boolean values: but we still want to encode them as such!
• Create boolean variables $x_{i,j,s}$ where $i,j \leq n^{k}$ and $s \in \gamma \cup Q$
• $\text{cell}\left\lbrack {i,j} \right\rbrack = s\Leftrightarrow x_{i,j,s} = \text{true} \land x_{i,j,s} = \text{false}\ \forall s \neq s$

For a nondeterministic Turing machine:

• The same table as the deterministic Turing machine:
• only the $\left( {i + 1} \right)^{\text{st}}$ configuration follows from the $i^{\text{th}}$ configuration using some nondeterministic choice

$\varphi = \varphi_{\text{cell}} \land \varphi_{\text{start}} \land \varphi_{\text{move}} \land \varphi_{\text{accept}}$

• $\varphi_{\text{cell}} = \land_{i,j}\left( {\vee_{s \in \Gamma \cup Q}\left( {x_{i,j,s} \land \neg\left( {\vee_{t \neq s}x_{i,j,t}} \right)} \right)} \right)$
• $\varphi_{\text{start}} = x_{1,1,\#} \land x_{1,2,q_{0}} \land x_{1,3,w} \land x_{1,4,w}\ldots$
• $\varphi_{\text{accept}} = \vee_{i,j}x_{i,j,q_{\text{accept}}}$: check if any cell is accepting

Window[i,j]: six cells of the table (six cells is convenient: 3x2, we need three to read the current, state, and next items)

• i.e. the window is size 3x2 because that’s exactly what we need to check that it is valid

$\varphi_{\text{move}} = \land_{1 \leq i \leq n^{k} - 1,1 \leq j \leq n^{k} - 2}\left( {\text{Window}\left\lbrack {i,j} \right\rbrack\ \text{is legal}} \right)$

note: pull examples, when there is no head the last two columns cannot change

… online lecture …

The following are equivalent:

1. $L \in \text{RP}$ (Randomized Polytime) if there is a probabilistic Turing machine that, on input $x$, runs in time $\text{poly}\left( |x| \right)$, and has a greater than or equal to 50% chance of reaching an accepting leaf.

   • $L \notin \text{RP}$ if the probabilistic Turing machine has a 0% chance of reaching an accepting leaf. (must reach reject state)

   	Algorithm’s Output	Accept	Reject
   Correct Output
   Accept		$\geq 50\%$ / true positive	$\leq 50\%$ / false negative
   Reject		0 / false positive	1 / true negative

2. $L \in \text{RP}$ if there is a PTM that, on input $x$, runs in time $\text{poly}\left( |x| \right)$ and has behavior:

   • $x \in L$: $\text{Pr}\left( \text{accept} \right) \geq 50\%$
   • $x \notin L$: $\text{Pr}\left( \text{reject} \right) = 100\%$

3. $L \in \text{RP}$ if there exists a deterministic polytime TM V such that:

   • $x \in L$: for at least half of all $y$ with $|y| = \text{poly}\left( |x| \right)$, $V\ \text{accepts}\ \left( {x,y} \right)$
   • $x \notin L$: for all y with $|y| = \text{poly}\left( |x| \right)$, $V\ \text{rejects}\ \left( {x,y} \right)$

…useful picture…

If there was an NP-complete language in RP, then RP would equal NP.

$L \in \text{NP}$ if there is a TM that, on input $x$, runs in time $\text{poly}\left( |x| \right)$ and has behavior: $\text{Pr}\left( \text{reaching accept} \right) > 0$

Definition. co-RP

$L \in \text{coRP}$ if there is a PTM that, on input $x$, runs in time $\text{poly}\left( |x| \right)$, and has the following behavior:

• $x \in L$ (strings in the language) have a 100% chance of being accepted
• $x \notin L$ have at least or equal to 50% chance of being rejected

$L \in \text{BPP}$ (Bounded-error Probabilistic Polytime) if there is a probabilistic Turing machine that, on input $x$, runs in time $\text{poly}\left( |x| \right)$ and has behavior:

• $x \in L$ if the probability of accepting is greater than $\frac{2}{3}$
• $x \in L$ if the probability of rejecting is greater than $\frac{2}{3}$
• ($\frac{2}{3}$ is arbitrary: we just need $\frac{p}{q} > \frac{1}{2}$)

…helpful diagram…

Modifying the definition of $\text{RP}$ a little bit: $L \in \text{RP}(p)$ if there is a PTM that, on input $x$, runs in time $\text{poly}\left( |x| \right)$ and has behavior:

• $\text{Pr}\left( \text{reaching accept} \right) \geq p$
• $\text{Pr}\left( \text{reaching reject} \right) = 1$