Cook-Levin Theorem

Question

In section 9.4.1 in our textbook, as well as in the following slide, we encountered this definition:

 

I could not understand why is the length of the CNF formula is O(f(n)^3), where f(n) is the steps for the NTM to decide a string of length n.

Can anyone explain it? Maybe some examples or illustration would be super helpful.

Thanks a bunch!

Answer 1

The construction of the CNF formula is the essence of the Cook Levin theorem.  The theorem itself is quite involved, but in the past people have presented that as their P4 project.  You can do a quick google search for that and find it.

The fact that the formula is polynomial in terms of f(n), is the key aspect of that.  The theorem shows that the solving a given problem instance using its NTM is equivalent to the formula being satisfiable.  Thus, CSAT is NP-hard.

Comments

Hi Prof, I have done google search but it seems too twisted. The major concern of mine is that why it is O(f(n)^3) - why is the power 3?

---

Twisted it is. :-)

---

Is the proof of this theorem required in in the exam? Or what kind of questions on this theorem is there?