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!