Monday, January 20, 2003

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

Prevous Lesson | Next Lesson

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.

  • qij: true if confi is in state j.
  • hik: true if the head in confi is at location k.
  • tikr: true if the tape cell in location k of confi 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. conf0 is the initial configuration.
  3. confm is accepting.
  4. For each i≤m, confi+1 follows from confi 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
qi0 OR qi1 OR ... OR qiu
Each configuration in at most one state. For each i and possible states v and w, v≠w
(NOT qiv) OR (NOT qiw)
2. Let x=x1...xn, b the blank character and state 0 the initial state. We have the following single variable clauses,
t0ixi for i≤n
t0ib for i>n
3. Let a be the accept state. We need only one single variable clause.
4. We need two parts. First if the head is not over a tape location then it should not change.
((NOT hik) AND tikr)→ ti(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
hik OR (NOT tikr) 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).

(qij AND hik AND tikr)→ NOT(t(i+1)ks AND hi(k-1) AND q(i+1)v)
which is equivalent to
(NOT qij) OR (NOT hik) OR (NOT tikr) OR (NOT t(i+1)ks) OR (NOT hi(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 hik) 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.

1 comment:

  1. I sincerly apologize for this intrusion. However, I would like to make a proposition. I developed and implemented a (fairly simple) algorithm that solves any CNF-SAT formula in polynomial time. I know, you think I am a "nut". However, the paper is only 4 pages and would require a minimal amount of effort to read. I would simply like for you to consider posting it on your blog for review. (I will also note that I have only posted this offer on this site.) Of course, you can review the paper first. I am absolutely not asking you to proofread it or test it. I know it works and I spent a considerable amount of time proofreading the paper and making it readable. Since the $1 million is always "looming" in the background, I will also mention that if the paper did end up receiving the price, it would be shared.

    Thank you,
    Jason Steinmetz
    Astoria, NY