I went through the midterm solutions at the beginning of class. These will not be posted online. If you want to discuss the solutions or the grading of the midterm, please see me during office hours or make an appointment.
Before we prove the Cook-Levin theorem (which is quite involved), we'll take a look at some examples of NP-complete problems. This will show us how varied and common NP-complete problems are, how to construct polynomial time reductions, and how useful the property of NP-completeness is for showing that a particular problem is difficult or complex.
A literal is a boolean variable or negated boolean variable, $x$ or $\overline x$. A clause is several literals connected with $\vee$. A boolean formula is in conjunctive normal form, called a CNF formula, if it comprises several clauses connected with $\wedge$. A formula is a 3-CNF formula if every clause has exactly three literals. Then $\mathrm{3SAT}$ is the following problem: Given a 3 CNF formula $\varphi$, is $\varphi$ satisfiable?
Theorem. $\mathrm{3SAT}$ is $\mathbf{NP}$-complete.
Proof. $\text{3SAT}$ is obviously in $\mathbf{NP}$ since every 3-CNF formula is a boolean formula. We will now reduce $\mathrm{SAT}$ to $\mathrm{3SAT}$.
(Note that we have not yet shown that $\mathrm{SAT}$ is $\mathbf{NP}$-complete. We will show this later, so we will assume this fact for now.)
First, we need to convert our arbitrary formula into a CNF formula. Every boolean formula can be rewritten into CNF by using standard techniques (distributivity, De Morgan's law, etc.). However, this can result in an exponential increase in size. Instead, we use the Tseytin transformation, which creates an equisatisfiable formula with only a linear increase in size. How this works is we introduce a new variable for each subformula and rewrite the formula to include "iff" clauses. Each of these clauses can be rewritten into CNF. For example $(a \vee b) \wedge c$ would be rewritten as $x_2 \wedge (x_1 \equiv a \vee b) \wedge (x_2 \equiv x_1 \wedge c)$. Then we can rewrite each iff clause into CNF, $$x_1 \equiv a \vee b = x_1 \to (a \vee b) \wedge (a \vee b) \to x_1 = (\overline{x_1} \vee p \vee q) \wedge (\overline p \vee x_1) \wedge (\overline q \vee x_1),$$
$$x_2 \equiv x_1 \wedge c = x_2 \to (x_1 \wedge c) \wedge (x_1 \wedge c) \to x_2 = (x_2 \vee \overline{x_1} \vee c) \wedge (x_1 \vee \overline{x_2}) \wedge (c \vee \overline{x_2}).$$Now, the formula is in CNF, but is not necessarily 3-CNF. First, we consider a clause $C$ of four literals, say $C = x_1 \vee \overline x_2 \vee \overline x_3 \vee x_4$. We add a new variable $z$ and replace $C$ with the clauses $C_1 = x_1 \vee \overline x_2 \vee z$ and $C_2 = \overline x_3 \vee x_4 \vee \overline z$. Then if $x_1 \vee \overline x_2 \vee \overline x_3 \vee \overline 4$ is True, then there is an assignment for $z$ that satisfies both $C_1$ and $C_2$. If $C$ is False, then no matter what we assign $z$, $C_1$ or $C_2$ will be false.
This method can then be applied to any clause of size $k > 3$ to obtain an equivlaent pair of clauses $C_1$ of size $k-1$ and $C_2$ of size $3$ made up of the variables of $C$ and a new variable $z$. We can apply this transformation repeatedly polynomially many times.
Now, what if a clause has fewer than three literals? For a two variable clause $(x_1 \vee x_2)$, we have $$(x_1 \vee x_2) = (x_1 \vee x_2 \vee y) \wedge (x_1 \vee x_2 \vee \overline y).$$ For a clause $x_1$, we have $$(x_1) = (x_1 \vee y \vee z) \wedge (x_1 \vee \overline y \vee z) \wedge (x_1 \vee y \vee \overline z) \wedge (x_1 \vee \overline y \vee \overline z).$$
Now, we simply check that $\varphi$ is satisfiable if and only if $\psi$ is satisfiable. $$\tag*{$\Box$}$$
Theorem. $\mathrm{CLIQUE}$ is $\mathbf{NP}$-complete.
Proof. We have already seen that $\mathrm{CLIQUE} \in \mathbf{NP}$. We reduce $\mathrm{3SAT}$ to $\mathrm{CLIQUE}$. In other words, we will construct a graph that contains a $k$-clique if and only if a given 3-CNF formula $\varphi$ is satisfiable.
Let $\varphi$ be a formula with $k$ clauses $$\varphi = (a_1 \vee b_1 \vee c_1) \wedge (a_2 \vee b_2 \vee c_2) \wedge \cdots \wedge (a_k \vee b_k \vee c_k).$$ We define a reduction $f$ that transforms $\varphi$ into a suitable graph $G$ and integer $k$.
We group nodes into threes which we call triples $t_1, \dots, t_k$, each of which corresponds to a clause in $\varphi$. We label each vertex of $G$ with a corresponding literal in $\varphi$.
We define edges of $G$ between every pair of vertices except between vertices of the same triple and between vertices which are contradictory, such as $x_1$ and $\overline x_1$.
Now we show that $\varphi$ is satisfiable of and only if $G$ has a $k$-clique. First, suppose that $\varphi$ has a satisfying assignment. Then at least one literal is true in every clause. In each tripe of $G$, we choose one vertex to correspond to a true literal in the assignment. These selected nodes form a $k$-clique, since they are all true (so they don't contradict each other), they are all in different triples, and we chose one vertex from each of the $k$ triples. Thus, $G$ contains a $k$-clique.
Next, suppose that $G$ has a $k$-clique. No two vertices of the same triple are in the clique, since they are not connected by an edge. Thus, each of the $k$ triples contains exactly one vertex in the $k$-clique. Then, we can assign truth values to the variables of $\varphi$ in such a way that each literal that corresponds to a clique node is assigned True. We can do this since there are no edges between nodes labeled by contradictory literals and such a pair of vertices would not be in the clique. Then we have a satisfying assignment, since each triple contains one node in the clique and so each clause contains at least one literal that evaluates to True. Thus, $\varphi$ is satisfiable. $$\tag*{$\Box$}$$