**P1**from Week 14 quiz questions (take home, to be done before Class 34)**P2**from Week 14 quiz questions (take home, to be done before Class 34)

A *clause* is of the form
$
C_i = l_1 \vee l_2 \vee \cdots \vee c_k
$
where each $l_j$ is what's called a *literal*.

A literal is simply a boolean variable, or its negation - i.e. $x_i$ or $\neg x_i$. Finially, a "3CNF" formula is a formula in CNF, with the added restriction that each clause has at most three literals.

So, for example the following is a 3CNF formula: $ (a \vee \neg b \vee \neg c) \wedge (\neg a \vee b \vee c) \wedge (\neg a \vee \neg c) $

Of course, the 3CNF-SAT problem is simply this: given a formula in 3CNF, is there an assignment of values to the formula's variables for which the formula evaluates to true?

Formulas in CNF are really nice to work with, because they have such a simple, regular structure. So most logic applications require their input to be in CNF. 3CNF is even more restricted. That restriction is really nice for analysis purposes, as we'll see in the following.

With these rules in place, we can convert a circuit to its formula equivalent. Here's what we do:

- number the gates $g_1,\ldots,g_k$ where the numbering is a topological sort. Note that this means that the last gate is the output for the whole circuit.
- for each gate $g_i$ create a variable $o_i$, so now we have the original variables $x_1,\ldots,x_n$ plus the new $o_i$ variables, one per gate.
- for each gate $g_i$ create formula $f_i$ using the above rules
- return formula $f_1 \wedge f_2 \wedge \cdots \wedge f_k \wedge o_k$

Example:

So, now that we have a polynomial time reduction from CIRCUIT-SAT to 3CNF-SAT, we've proved the following:

**Theorem:** 3CNF-SAT is NP-Complete.

We prove this by giving a polynomial time reduction of 3CNF-SAT to INDEPENDENT-SET. So, we're given a 3CNF formula. Let $k$ be the number of clauses in the formua. We create a graph that has $k$ "clusters" of vertices, one cluster for each clause. A cluster for clause $C_i = (l_{i,1} \vee l_{i,2} \vee l_{i,3})$ consists of three vertices, each labeled with one of the three literals from the clause. If the clause only has 2 (or 1) literal, the cluster will only have 2 (or 1) vertices. Each vertex in a cluster is connected by an edge to every other vertex in the cluster. Also, a vertex in a given cluster labeled with literal $l$ has an edge to every vertex in the other clusters labeled $\neg l$. The claim is that this graph has an independent set of size $k$ if and only if the original formula is satisfiable.

**Example:** This example shows the graph derived from
a 3CNF formula. The resulting INDEPENDENT-SET problem has
$k=3$, since the formula has three clauses. In green, the
vertices comprising an independent set of size 3 are circles.
Notice that they correspond to a satisfying assignment of
values to variables in formula.