Cook-Levin Theorem

+2 votes

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!

asked Dec 6, 2016 in NP-Completeness by Roc6212 AlgoMeister (748 points)

1 Answer

+1 vote
Best answer
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.
answered Dec 6, 2016 by Amrinder Arora (38 points)
selected Dec 6, 2016 by Roc6212
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?
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc