Research Paper on Cook-Levin Theorem

Introduction

This paper explains the Cook-Levin Theorem: Computation is Local, defines the notation NP which stands for non-deterministic polynomial-time which can also be described using a variant of Turing machines called non-deterministic Turing machines (abbreviated NDTM). This paper has also discussed some examples of NP-complete problems and provided a proof for the Cook-Levin Theorem.

Is your time best spent reading someone else’s essay? Get a 100% original essay FROM A CERTIFIED WRITER!

Save 25%

This problem mostly comes from propositional logic. Example, a Boolean formula over the variables (m1 . . . mn ), consists of the variables and the logical operators AND (^), NOT () and OR (n):

a ^ b) n (a c) n (b c) is a Boolean equation that is True if and just if most of the variables a, b, c are True. Boolean technique over variables (m1 . . . mn ) is in CNF shape (shorthand for Conjunctive Normal Form) in the event that it is an AND of ORs of variables or their negations. For instance, the accompanying is a 3CNF equation: (m1 nm2 n m3 )m2nm3 m4 ( m1 n m3 n m4 ).

Theorem

Give SAT a chance to be the language of all satisfiable Conjunctive Normal Form (CNF) formulae, and 3SAT be the language of all satisfiable 3CNF formulae. At that point:

1. SAT is NP-complete.
2. 3SAT is NP-complete.

Both SAT and 3SAT are clearly in NP since a satisfying assignment can serve as the certificate that formula is satisfiable. Thus we need to prove that they are NP-hard, this is done by first establishing that SAT (Satisfiability) is NP-hard and then showing that SAT (Satisfiability) is polynomial-time Karp reducible to 3SAT (3-Satisfiability). This implies that 3SAT (3-Satisfiability) is NP-hard by the transitivity of polynomial-time reductions. Thus the following lemma is the key to the proof; SAT is NP-hard. Note that to demonstrate this, we need to show how to lessen each NP dialect L to SAT (Satisfiability), as it were, give a polynomial-time transformation that turns any x {0, 1} into a Conjunctive Normal Form (CNF) equation x such that x L iff x is satisfiable. Since we don't know anything about the dialect L with the exception of that it is in NP, this lessening has to depend just upon the meaning of calculation and express it in some way using a Boolean recipe.

The formula (a n b) ^ (a n b) is in CNF form. It is satisfied by only those values of a, b that are equal. Thus, the formula ((x1 n y1 ) ^ (x1 n (y1 ) ^ ^ ( xn yn ) ^ (xn n yn) is True if and only if the strings x,y0,1n are equal. Thus, though = is not a standard Boolean operator like n or , we will use it as a convenient Shorthand since the formula (1 =(2) equivalent to (1 n 2 ) 1 n 2). Conjunctive Normal Form (CNF) formulae of sufficient size can express every Boolean condition, as shown by the following simple claim: (this fact is sometimes known as the universality of the operations AND, OR

and NOT). Application: For every Boolean function f: 0,1e {0, 1} there is an e-variable CNF formula of size e2e such that ( m)=f(m) for every m 0,1e where the scope of a CNF equation is characterized to be the quantity of /n symbols it contains.

Proof

For every n 0,1e it is not hard to see that there exists a clause Cv such that Cv (v)=0 and Cv( m)=1 for every mv. For example, if v={1, 1, 0, 1} the corresponding clause is

m1 n m2 n m3 n m4 We let be the AND of all the clauses Cv for v such that fv=0. Then for every m such that f(m)=0 it holds that Cu(u)=0 and hence m is also equal to 0. On the other hand if fm=1 then Cv( m)=1 for every v such that f(v)=0 and hence m=1 . We get that for every u, m=f(u)

Proof that SAT is NP-hard

Let L be an NP language and let M be the polynomial time TM such that that for every

x {0,1}*, x L M(x, u)=1 for some u 0,1pIxI Where p: N N is some polynomial. We show L is polynomial-time Karp reducible to SAT by describing a way to transform in polynomial-time every string x 0,1* into a CNF formula (x such that x L iff is satisfiable. The function that maps u 0,1pIxI to M(x, u) can be expressed as a CNF formula Psx for every u 0,1pIxI thus a string u M(x, u)=1 exists if and only if Psx is satisfiable. But this is not useful here since the size of the formula obtained in the claim can be as large as pIxI2pIxI. To get a smaller formula, we use the fact that M runs in polynomial time, and that each essential step of a Turing machine is highly local.

The following simplifying assumptions will be made about the TM M in the course of the proof: M only has two tapes: an input tape and a work/output tape, M is an oblivious TM in the sense that its head movement does not depend on the contents of its input tape. In particular, this means that M's calculation takes the same time for all inputs of size n and for each time step I the area of M's heads at the ith level depends only on i and M's input length.

These assumptions can be made without loss of generality because for every T-time TM M there exists a two-tape oblivious TM M computing the same function in OTn2 time. Thus in particular if L is in NP, then there exists a two-tape oblivious polynomial-time TM M and a polynomial p such that x L u 0,1pIxIsuch that M(x, u)=1 The advantage of assuming that M is unaware is that for any given input length, we can define functions inputposi and prev(i ) where inputposi denotes the location of the input tape head at the ith step and prev(i) signifies the last step before i that M visited the same place on its work tape. These values can be processed in polynomial time by simulating M on, say, each of the zeroes input.

Let n N and x 0,1nwe need to construct a CNF formula x such that x L x SAT. Recall that x L and only if there exists some u 0,1pn such that M(y)=1 where y=xou o denotes concatenation. Since the sequence of snapshots in M's execution completely determines its outcome, this happens if and only if there exist a string y 0,1n+pn and a sequence of strings Z1...ZT 0,1c satisfying the following conditions:

The first n bits of y is equal to x.

The string Z1 encodes the initial snapshot of M

For every i 2...T Zi=F(Zi-1 Zinputpos(i), Zprev(i)

The last string ZT encodes a snapshot in which the machine halts and outputs 1.

Since both SAT and 3SAT are clearly in NP then this completes the proof that SAT is NP-complete. Now the final proof of this theorem is to prove that SAT P 3SAT.

Proof

Here we map a CNF formula into a 3CNF formula Ps such that Ps is satisfiable if and only if is. We demonstrate the first case that is a 4CNF. Let C be a clause of say C=(m1 ((m2) n m3 n m4 ) . A new variable Z is added to the and replace C with the pair of clauses C1= (m1 (m2) n z) and C2=m3 n m4 n z. Clearly, if (m1 (m2) n m3 n m4 ) is true then there is an assignment to z that satisfies both (m1 (m2) n z) and m3 n m4 n z. What's more, the other way round. In the event that C is false, at that point regardless of what esteem we assign to z either C1 or C2 will be false. The same thought can be connected to a general clause of size 4, and truth be told, can be used to change each clause C of size k. to an equivalent pair of clauses C1 of size k 1 and C2 of size three that depend on the k variables of C and an additional auxiliary Variable z. Applying this transformation repeatedly yields a polynomial-time transformation of a CNF formula into an equivalent 3CNF formula Ps.

Conclusion

In conclusion, The Cook-Levin theorem is an excellent example of the power of abstraction. Even though the theory holds regardless of whether our computational model is the C programming language or the Turing machine, it might have been considerably all the more difficult to discover in the previous setting. Also, it merits bringing up that the evidence yields a result that is somewhat stronger than the theorem's statement. One can also confirm that the confirmation supplied a balanced and onto outline the set of certificates for x and the set of satisfying assignments for f(x), inferring that they are of the same size.

Bibliography

S. Arora and B. Barak. Computational Complexity. 2007