Foundations of Complexity Lesson 14: CNF-SAT is NP-complete

We will show that CNF-SAT is NP-complete. Let A be a language in NP accepted by a nondeterministic Turing machine M. Fix an input x. We will create a 3CNF formula φ that will be satisfiable if and only if there is a proper tableau for M and x.

Let m be the running time of M on x. m is bounded by a polynomial in |x| since A is in NP. m is also a bound on the size of the configurations of M(x).

We will create a set of Boolean variables to describe a tableau and a set of clauses that will all be true if and only if the tableau is proper. The variables are as follows.

• q_ij: true if conf_i is in state j.
• h_ik: true if the head in conf_i is at location k.
• t_ikr: true if the tape cell in location k of conf_i has element r.

We create four clause groups to check that the tableau is proper.

1. Every configuration has exactly one state, head location and each tape cell has one element.
2. conf₀ is the initial configuration.
3. conf_m is accepting.
4. For each i≤m, conf_i+1 follows from conf_i in one step.

1. We will just do this for states. The others are similar. Suppose we have u possible states.

Each configuration in at least one state. For each i we have
q_i0 OR q_i1 OR ... OR q_iu Each configuration in at most one state. For each i and possible states v and w, v≠w
(NOT q_iv) OR (NOT q_iw)    2. Let x=x₁...x_n, b the blank character and state 0 the initial state. We have the following single variable clauses,
q₀₀
h₀₁
t_0ixi for i≤n
t_0ib for i>n 3. Let a be the accept state. We need only one single variable clause.
q_ma   4. We need two parts. First if the head is not over a tape location then it should not change.
((NOT h_ik) AND t_ikr)→ t_i(k+1)r   Now this doesn't look like an OR of literals. We now apply the facts that P→Q is the same as (NOT P) OR Q and NOT(R AND S) is equivalent to (NOT R) OR (NOT S) to get

h_ik OR (NOT t_ikr) OR t_(i+1)kr   At this point none of the formula has been dependent on the machine M. Our last set of clauses will take care of this. Recall the program of a Turing machine is a mapping from current state and tape character under the head to a new state, a possibly new character under the head and a movement of the tape head one space right or left. A nondeterministic machine may allow for several of these possibilities. We add clauses to prevent the wrong operations.

Suppose that the following is NOT a legitimate transition of M: In state j and tape symbol r, will write s, move left and go to state v. We prevent this possibility with the following set of clauses (for all appropriate i and k).

(q_ij AND h_ik AND t_ikr)→ NOT(t_(i+1)ks AND h_i(k-1) AND q_(i+1)v)    which is equivalent to

(NOT q_ij) OR (NOT h_ik) OR (NOT t_ikr) OR (NOT t_(i+1)ks) OR (NOT h_i(k-1)) OR (NOT q_(i+1)v)    We do this for every possible illegitimate transition. Finally we just need to make sure the head must go one square right or left in each turn.

(NOT h_ik) OR h_(i+1)(k-1) OR h_(i+1)(k+1)   Just to note in the above formula we need special care to handle the boundary conditions (where k is 1 or m) but this is straightforward.