Reading

These notes and Unit 6 sections 6 and 7.

Homework

Homework

Problems with the obvious "reduction" of CIRCUIT-SAT to SAT

If we have a Problem Y in NP and we would like to prove that it is NP-COMPLETE, all we have to do is poly time reduce a known NP-COMPLETE problem to Y. That was our conclusion from last class. An obvious first thing to try is to reduce CIRCUIT-SAT to "SAT", which is this: given a boolean formula, is there an assignment of values to variables that makes the formula true?

There is a simple algorithm for doing this conversion. First, we will assume the circuit has only ands, ors and nots, and that the ands/ors have eatly two inputs, and the nots have exactly one input. If the curcuit doesn't satisfy these properties, it can be modified so that it does, and the new circuit is at most a constant factor larger than the original. 

Algorithm: mkf(C,u)
Inputs: Circuit C (as described above) and node u in the circuit
Output: Boolean formula F equivalent to C
---------------------------------------
if node u is variable xi, return formula xi
if u is an "and" gate
   let v and w be the nodes that feed into u
   return formula ( mkf(G,v) ) ∧ ( mkf(w) )
else if u is an "or" gate
   let v and w be the nodes that feed into u
   return formula ( mkf(G,v) ) ∨ ( mkf(w) )
else
   let v be the node that feeds into u
   return formula ¬( mkf(F,v) )

It's easy to prove (with induction!) that for circuit C with output node u, the formula mkf(C,u) is equivalent to the circuit, meaning that any assignment of values to the xi's that satisfies the circuit satisfies the formula and vice versa. Here's an example: 
      Circuit C
                 .___
      x1---NOT---|and\___    mkf(C,"the and gate") = (¬(x1)) ∧ (x2)
      x2---------|___/
Unfortunately, this does not give us a polynomial time reduction. We looked in class at an example of a family of inputs for which this algorithm produces exponentially larger formulas than circuits. 
      C1 = x1,

      Cn = Cn-1--------------OR---
               \____.---.    /
           xn-------|xor|---'
                    `---'
The size of this circuit in number of edges is 4*(n-1) and in vertices is n + 2*(n-1). Either way, it's linear in $n$. Algorithm mkf produces the formula $$F_1 = x_1,\ \ \ F_n = F_{n-1} \vee \left(F_{n-1} \oplus x_n\right)$$ ... which has more than $2^{n-1}$ operators.

3CNF-SAT

A propositional (boolean) formula $F$ is in Conjunctive Normal Form if it has the following form: $ F = C_1 \wedge C_2 \wedge \cdots \wedge C_n $ where each $C_i$ is what's called a clause.

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.

3CNF-SAT is NP-Complete

In the below, we'll give a polynomial time reduction of CIRCUIT-SAT to 3CNF-SAT. First, we observe that we can take a circuit and expand it slightly (i.e. polynomially) to produce an equivalent circuit containing only AND, OR and NOT gates, and in which the AND and OR gates have only two inputs each. We discussed this in class. Now consider the following conversion of gate to 3CNF formula:

With these rules in place, we can convert a circuit to its formula equivalent. Here's what we do:
  1. 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.
  2. 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.
  3. for each gate $g_i$ create formula $f_i$ using the above rules
  4. return formula $f_1 \wedge f_2 \wedge \cdots \wedge f_k \wedge o_k$
The original circuit is satisfiable if and only if the formula is satisfiable (the proof is the same as the proof we gave for the conversion to SAT) and the process is clearly polynomial time. The idea behind the translation is that each $f_i$ encodes the assertion that the gate functions properly, for example that an AND-gate really outputs the "and" of its inputs. So the formula specifies that "gate 1 operates correctly, and cate 2 operates correctly, .... and gate $k$ operates correctly, and gate $k$ outputs TRUE".

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.

The INDEPENDENT-SET Problem

So far, all the problems that we've proven to be NP-Complete are closely-related problems ... all three are really about logic. Now let's consider a very different problem: a graph problem. The INDEPENDENT-SET Problem is this: Given unweighted, undirected graph $G$, and positive integer $k$, is there an independent set in $G$ of size $k$? Note: an independent set is a set of vertices from $G$ that have no edges between them.

INDEPENDENT-SET is NP-Complete

Theorem: INDEPENDENT-SET 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.

NP-Complete Problems Surround Us!

For better or for worse, the world is full of NP-Complete problems. See Wikipedia's list of NP-Complete Problems. This includes problems like HAM-CYCLE, O/1-KNAPSACK, SIMPLE-KNAPSACK, HITTING-SET, PARTITION, and many, many more.