2026/09/02 TOC Scribe
$\newcommand{SAT}{\mathsf{SAT}}$ $\newcommand{TSAT}{\mathsf{3SAT}}$ $\newcommand{NP}{\mathbf{NP}}$ $\newcommand{BS}{{0, 1}}$
3-Conjunctive Normal Form (3CNF)
Suppose you have some $m$ boolean variables $v_i$ where $i\in[m]$. We construct a clause using exactly three of them in the following fashion $$(x_{i_1} \lor x_{i_2} \lor x_{i_3})$$ Where $i_1, i_2, i_3 \in[m]$ and $x_{i}\in{v_i, \neg{v_i}}$
That is a clause is a conjunction of exactly three variables. These variables can be themselves or their negations.
A 3CNF is just a disjunction of these conjunctive clauses.
We can represent this using $\bigwedge_i \left(\bigvee_j v_{i_j} \right)$
$\mathsf{3SAT}$
$\mathsf{3SAT}$ is deciding whether a 3CNF formula is satisfiable or not. Mathematically
$$ \mathsf{3SAT(\psi)} = \begin{cases} 1,\exists x\text{ s.t. } \psi(x) = 1\ 0,\text{ o.w.} \end{cases} $$
Theorem 1: Cook-Levin Theorem [Coo71,Lev73]
- $\mathsf{SAT}$ is $\mathbf{NP}$-complete
- $\mathsf{3SAT}$ is $\mathbf{NP}$-complete
Notice how simple the claim looks, rather, how deficient of assumptions it is. We’re saying that $\SAT$ and $\TSAT$ are $\NP$-complete which means that they are in $\NP$ and every other problem in $\NP$ is polynomial-time reducible to it. The first claim is very easy to see. But, what about the second one? How can you, without any information about a language $L$, except that it is in $NP$, reduce it to $\SAT$? Reductions are notoriously hard. If you look at the web of all reductions we’ve done, you’ll see that it looks like a tree rather than a complete graph. We cannot reduce any problem to any other problem directly. The two problems need to have something in common or a duality that would allow us to perform the reduction. We then repeatedly compose reductions. But here there are no known reductions that we can use - we don’t even know how $L$ looks like.
As you’ll see the reduction to $\SAT$ is the reduction that everyone uses to do their own. Hence, it cannot depend on anything. This is the tricky part. To reduce every problem, without any knowledge about them, to $\SAT$.
Claim 2: Universality of AND, OR, NOT
$\forall$ boolean functions $F:\BS^l\rightarrow\BS$ and therefore languages $L$ described by $x\in L\iff F(x) = 1$, $\exists$ a l-CNF formula $\varphi$ of size $l2^l$ such that $F(x) =\varphi(x), \forall x\in\BS^l$
To prove this claim, let us first think about a weaker claim:
$\forall x \in \BS^l,\exists$ an $l$ variable conjunctive clause $\varphi_x$ such that $\varphi_x(x) = 1$ and $\varphi_x(u) = 0, \forall u\ne x$
Meaning for any l-length binary string we can construct a l-variable conjunctive clause such that the only solution to satisfy it is the string itself.
We construct these conjunctive clauses for all the $x\notin L$ and disjunct them together.
$$\Phi = \bigwedge_{x\notin L}\left( \varphi_x \right)$$