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.

- Every configuration has exactly one state, head location and each tape cell has one element.
- conf
_{0}is the initial configuration. - conf
_{m}is accepting. - For each i≤m, conf
_{i+1}follows from conf_{i}in one step.

Each configuration in at least one state. For each i we have

_{i0}OR q

_{i1}OR ... OR q

_{iu}

_{iv}) OR (NOT q

_{iw})

_{1}...x

_{n}, b the blank character and state 0 the initial state. We have the following single variable clauses,

_{00}

h

_{01}

t

_{0ixi}for i≤n

t

_{0ib}for i>n

_{ma}

_{ik}) AND t

_{ikr})→ t

_{i(k+1)r}

_{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).

_{ij}AND h

_{ik}AND t

_{ikr})→ NOT(t

_{(i+1)ks}AND h

_{i(k-1)}AND q

_{(i+1)v})

_{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})

_{ik}) OR h

_{(i+1)(k-1)}OR h

_{(i+1)(k+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.

ReplyDeleteThank you,

Jason Steinmetz

Astoria, NY