+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!

in NP-Completeness by AlgoMeister (752 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.
by AlgoMeister (1.6k points)
selected by
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?

Related questions

+1 vote
2 answers
0 votes
3 answers
asked Dec 20, 2019 in NP-Completeness by Amrinder Arora AlgoMeister (1.6k points)
+4 votes
4 answers
asked May 6, 2018 in NP-Completeness by zzkaing Active (268 points)
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...